Editorial: Maximum Subarray

1 Intuition

The key insight is that at each position, we decide: should we extend the current subarray or start a new one? We keep track of the maximum sum ending at the current position and update our global maximum. Kadane's algorithm is a greedy approach that achieves O(n) time complexity, much better than checking all subarrays O(n²).

2 Approach

1. Initialize `max_current` and `max_global` to the first element 2. Iterate through array starting from second element: - `max_current = max(element, max_current + element)` - Either extend previous subarray or start new one - `max_global = max(max_global, max_current)` - Update global maximum 3. Return `max_global`

3 Complexity Analysis

**Time Complexity:** O(n) - single pass through array **Space Complexity:** O(1) - only use two variables Kadane's algorithm is optimal for this problem.

4 Solution Code

def maxSubArray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    return max_global

int maxSubArray(vector<int>& nums) {
    int max_current = nums[0], max_global = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        max_current = max(nums[i], max_current + nums[i]);
        max_global = max(max_global, max_current);
    }
    return max_global;
}

5 Code Walkthrough

For [-2,1,-3,4,-1,2,1,-5,4]: - Start: max_current=-2, max_global=-2 - 1: max_current=max(1,-2+1)=1, max_global=1 - -3: max_current=max(-3,1-3)=-2, max_global=1 - 4: max_current=max(4,-2+4)=4, max_global=4 - -1: max_current=max(-1,4-1)=3, max_global=4 - 2: max_current=max(2,3+2)=5, max_global=5 - 1: max_current=max(1,5+1)=6, max_global=6 - -5: max_current=max(-5,6-5)=1, max_global=6 - 4: max_current=max(4,1+4)=5, max_global=6 Result: 6 (subarray [4,-1,2,1])