53. Maximum Subarray

LeetCode

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // choose: if follow the previous ones, or reset from the current
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

Remarks:

  1. TC: $O(n)$; SC: $O(1)$
  2. Main Idea: When traverse each index, we consider: is it better to follow the previous ones (currentSum + nums[i]), or start with the new number nums[i], as the ones is bigger enough?
  3. Known as: Kadane’s Algorithm