Problem #53: Maximum Subarray

Intuition & Strategy Breakdown

Use Kadane's Algorithm. Maintain a running maximum subarray sum ending at current index. Reset running sum to current element if running sum drops below zero.

Python Solution

def maxSubArray(nums):
    max_so_far = current_max = nums[0]
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        max_so_far = max(max_so_far, current_max)
    return max_so_far

Java Solution

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int currentMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        return maxSoFar;
    }
}