最大子数组

题目链接

53. 最大子数组

解题思路

如果前面的和为负就丢掉重新开始，同时更新全局最大值。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];
        int max = nums[0];

        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }

        return max;
    }
}

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(1)$