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中文网其他相关文章！