Maximum Subarray

Problem Statement

You’re on a treasure hunt in an array of integers, seeking the contiguous subarray with the largest sum. This easy-level DP classic (Kadane’s Algorithm) is a gold miner’s dream—find the richest streak amidst ups and downs! Return the maximum sum.

Example

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6 ([4, -1, 2, 1])

Input: nums = [1]

Output: 1

Input: nums = [-1, -2, -3]

Output: -1 (Best is [-1])

Code

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

def max_sub_array(nums):
    max_so_far = nums[0]
    max_ending_here = nums[0]
    for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
            

function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
            

Explanation

• DP Insight: At each step, decide to start anew or extend the current subarray.
• Flow: maxEndingHere tracks the best sum ending at i; maxSoFar keeps the global max.
• Example Walkthrough: [-2,1,-3,4,-1,2,1] → maxEndingHere=-2,1,-2,4,3,5,6; maxSoFar=6.
• Relevance: Kadane’s is a cornerstone for array-based DP problems.
• Edge Case: Works even with all negatives—picks the least bad option.

Note