Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Approach: Kadane’s Algorithm (O(n))

Algorithm

1. Maintain two values: currentSum (the maximum sum of a subarray ending at the current position) and maxSum (the global maximum)
2. For each element, decide whether to extend the current subarray (currentSum + num) or start a new one (num)
3. Update maxSum after each step
4. Return maxSum

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - constant extra space

Java Implementation

public class MaximumSubarray {

    /**
     * Find the largest sum of any contiguous subarray.
     * @param nums Input array
     * @return Maximum subarray sum
     */
    public static int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]");
        System.out.println("Output: " + maxSubArray(nums1)); // Expected: 6

        int[] nums2 = {1};
        System.out.println("Input: nums = [1]");
        System.out.println("Output: " + maxSubArray(nums2)); // Expected: 1

        int[] nums3 = {5, 4, -1, 7, 8};
        System.out.println("Input: nums = [5, 4, -1, 7, 8]");
        System.out.println("Output: " + maxSubArray(nums3)); // Expected: 23
    }
}

Alternative Approach: Divide and Conquer (O(n log n))

Split the array in half. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. The crossing case is the maximum sum of the left suffix plus the right prefix.

public class MaximumSubarrayDivideConquer {

    public static int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private static int helper(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return nums[lo];
        }

        int mid = lo + (hi - lo) / 2;

        int leftMax = helper(nums, lo, mid);
        int rightMax = helper(nums, mid + 1, hi);

        // Crossing subarray: best left suffix + best right prefix
        int leftSuffix = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= lo; i--) {
            sum += nums[i];
            leftSuffix = Math.max(leftSuffix, sum);
        }

        int rightPrefix = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += nums[i];
            rightPrefix = Math.max(rightPrefix, sum);
        }

        int crossMax = leftSuffix + rightPrefix;

        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
}

Time & Space Complexity

• Time Complexity: O(n log n) - each level processes O(n) elements
• Space Complexity: O(log n) - recursion stack

Example Walkthrough

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

1. i=0, num=-2: currentSum=max(-2, -2)=-2. maxSum=-2
2. i=1, num=1: currentSum=max(1, -2+1)=-1 -> 1. maxSum=1
3. i=2, num=-3: currentSum=max(-3, 1-3)=-2. maxSum=1
4. i=3, num=4: currentSum=max(4, -2+4)=4. maxSum=4
5. i=4, num=-1: currentSum=max(-1, 4-1)=3. maxSum=4
6. i=5, num=2: currentSum=5. maxSum=5
7. i=6, num=1: currentSum=6. maxSum=6
8. i=7, num=-5: currentSum=1. maxSum=6
9. i=8, num=4: currentSum=5. maxSum=6

Answer: 6 (subarray [4, -1, 2, 1]).

Key Points

1. Greedy Reset: When currentSum turns negative, it is better to start a new subarray
2. Kadane’s Insight: The best subarray ending at i is either nums[i] alone or the best subarray ending at i - 1 plus nums[i]
3. Handles All-Negative Arrays: Initializing with nums[0] handles arrays where every element is negative
4. Divide and Conquer Alternative: The crossing case ties the two halves together
5. O(1) Space: Kadane’s algorithm uses only two variables