Intuition

We can build the intuition based on the two-point approach.

Approach

We will start with two variables maxSum and maxTillNow.

• The first variable stores the max sum we have attained overall in the array.

• The second variable stores the value of the maximum sum attained till the current index. Since the array has a negative value, this value will fluctuate, but whenever we get maxSum < maxTillNow, we update the maxSum.

• The final case we have to handle will be if the maximum sum till any index reaches zero, i.e., maxTillNow < 0, reset the maxTillNow = 0 at the end of loop.

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

Code

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

原文链接：Kadane’s Algorithm: Leetcode 53 Maximum subarray