Kadane 演算法：Leetcode 最大子數組

直覺

我們可以基於兩點法建立直覺。

方法

我們將從兩個變數 maxSum 和 maxTillNow 開始。

• 第一個變數儲存我們在陣列中獲得的總和的最大和。

• 第二個變數儲存直到目前索引為止達到的最大總和的值。由於陣列有一個負值，這個值會波動，但每當我們得到 maxSum

• 我們必須處理的最後一種情況是，直到任何索引為止的最大總和達到零，即 maxTillNow

複雜

• 時間複雜度：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
Leetcode簡介：Leetcode：devn007

以上是Kadane 演算法：Leetcode 最大子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！