Maximum Sum of Continuous Subarray

Given an array with integers, find the largest sum of continuous subarray. This maximum subarray problem was first posed in 1977. Jay Kadane solved it in linear time (O(n)) in 1988.

The Approach

The brute-force way of solving this is to use 2 for-each loops, one inside another, to loop through all combination. However, the linear approach is to use dynamic programming to break down the problem into small ones.

Characteristics of dynamic programming:

1. Optimal substructure - The solution to a problem in a bigger set can be efficiently represented in terms of a solution to a problem in an incrementally smaller set. That is, problem can be divided into stages.
2. Recursive nature of the solution.
3. Bottom-Up (solve smaller problems first)

Thought Process

The bigger problem is to find all the combination of contiguous subarrays of a given array A. Among all the combination of contiguous subarrays, find the maximum sum. A smaller problem is to find the maximum sum of contiguous subarray of a given smaller array.

When you add an element to a smaller array, "the max of possible sub sequence sum of the bigger array that includes the last element as part of the sum" is either the added element itself, or "the previous max of possible sub sequence sum of the bigger array that includes the previous added element as part of the sum" plus the newly added element. The recursive nature of the solution is:

m(i) = the max of possible sub sequence sum of the array that includes the last element as part of the sum
      = max{m(i-1)+A[i], A[i]}

For example, let's say A = {-9,-8,17,1,-1,0,1}

m(1) = -9
m(2) = max(-9-8, -8) = -8
m(3) = max(-8+17, 17) = 17
m(4) = max(17+1, 1) = 18
m(5) = max(18-1, -1) = 17
m(6) = max(17+0, 0) = 17
m(7) = max(17+1, 1) = 18

The answer is the max of all possible m(i).

max(m(i)) = 18

Code Sinppet

class Test{
  public static int maxSubarraySum(int[] A){
    int m = -99999;
    int max_subarray_sum = m;
    for(int i=0; i<A.length; ++i){
      m = Math.max(m + A[i], A[i]);
      max_subarray_sum = Math.max(max_subarray_sum, m);
    }
    return max_subarray_sum;
  }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] input1 = {2,3,-1};
    int[] input2 = {-9,-8,17,1,-1,0,1};
    int[] input3 = {0,-1,1,1,-1,0,1};
 
    System.out.println(maxSubarraySum(input1)); // print 5
    System.out.println(maxSubarraySum(input2)); // print 18
    System.out.println(maxSubarraySum(input3)); // print 2
  }
}

References

How can I effectively practice Dynamic Programming to improve my skills?