Data Structures & Algorithms (Arrays & Strings): 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.

Playground: Leetcode 53

Nested Loops Approach (Brute Force)

Use two nested loops to iterate over all possible subarrays, compute their sums incrementally, and keep track of maximum sum found.

Visualization

Algorithm

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
	
    for(int i = 0; i < nums.length; i++) {
        int currentSum = 0;
        for(int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }

    return maxSum;
}

Time Complexity

For each start index i, the inner loop runs from i to n - 1. That yields n + (n - 1) + (n - 2) + ... + 1 iterations, which simplifies to n(n + 1) / 2. Ignoring constants and lower-order terms, the overall time complexity = O(n²).

Space Complexity

We only use a few scalar variables such as maxSum, currentSum, i, and j. Since, only constant extra space is used, the overall space complexity = O(1).

Key Observation

At any index = i, if the previous subarray sum is negative, carrying it forward only reduces your current sum.

For example, in [-2, 1], it's better to start a new subarray at index = 1 (i.e., [1]) rather than expanding the previous array (i.e., [-2]) to [-2, 1].

NOTE: At every index, you decide: "Should I start a new subarray from here, or continue expanding the previous one?"

Kadane's Algorithm

Iterate through the nums array, updating the current subarray sum by choosing between expanding the previous subarray or starting a new one, while keeping track of the maximum sum found.

Visualization

Algorithm

public int maxSubArray(int[] nums) { 
    int maxSum = nums[0];
    int currentSum = 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;
}

Time Complexity

We are only iterating through the nums array once. Considering the operations performed inside each iteration take constant time, the overall time complexity = O(n).

Space Complexity

Consideing no extra space is used, the overall space complexity = O(1).