Skip to content

Maximum Sub-array sum

Info

This content was generated by Gemini.

The Maximum Subarray Problem, which challenges us to find the contiguous subarray with the largest sum within a given array, is a classic problem in computer science. While it can be solved using various approaches, two stand out for their efficiency and elegance: Kadane's Algorithm and a more explicit dynamic programming formulation.

Understanding the Optimal Substructure

At its core, the Maximum Subarray Problem exhibits the property of optimal substructure, a hallmark of problems amenable to dynamic programming. This means that the optimal solution to the problem can be constructed from the optimal solutions to its subproblems.

To illustrate, consider an array nums. Let dp[i] represent the maximum sum of a contiguous subarray ending at index i. We can define dp[i] recursively:

dp[i] = max(nums[i], dp[i-1] + nums[i])

This equation states that the maximum subarray sum ending at index i is either the element at i itself, or the maximum subarray sum ending at the previous index i-1 plus the element at i. This recursive relationship demonstrates how the solution to a larger subproblem (dp[i]) is built from the solution to a smaller subproblem (dp[i-1]).

Kadane's Algorithm: Optimized Dynamic Programming

Kadane's Algorithm is, in essence, an optimized version of this dynamic programming approach. Instead of storing the maximum sums for all subarrays ending at each index in an array (like the dp array in the explicit dynamic programming solution), Kadane's Algorithm maintains only two variables:

maxEndingHere: The maximum sum of a subarray ending at the current index.

maxSoFar: The overall maximum sum found so far.

By eliminating the need for the dp array, Kadane's Algorithm reduces the space complexity from to , while retaining the same time complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

Why Kadane's is Dynamic Programming

Kadane's Algorithm embodies the principles of dynamic programming:

Optimal Substructure: It leverages the optimal substructure property by iteratively building the solution (maxEndingHere) based on the optimal solution to the previous subproblem (the previous value of maxEndingHere).

Overlapping Subproblems: Although not explicitly stored, the calculation of maxEndingHere at each step reuses the result of the previous step, demonstrating the concept of overlapping subproblems.

In essence, Kadane's Algorithm is a space-optimized implementation of dynamic programming. It achieves the same result as the explicit DP approach but with significantly reduced memory usage.