Kadane&#s アルゴリズム: Leetcode 最大部分配列

直感

2 点アプローチに基づいて直感を構築できます。

アプローチ

2 つの変数 maxSum と maxTillNow から始めます。

• 最初の変数には、配列全体で得られた最大合計が格納されます。

• 2 番目の変数には、現在のインデックスまでに達成された最大合計の値が格納されます。配列には負の値があるため、この値は変動しますが、maxSum

• 処理しなければならない最後のケースは、いずれかのインデックスがゼロに達するまでの最大合計が、つまり maxTillNow < になる場合です。 0、ループの最後で maxTillNow = 0 をリセットします。

複雑

• 時間計算量: O(N)

• 空間複雑さ: O(1)

コード

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}

その他のソリューションの GitHub リポジトリ: Git
リートコード プロフィール: リートコード: devn007

以上がKadane&#s アルゴリズム: Leetcode 最大部分配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。