## The Approach

Characteristics of dynamic programming:

- 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.
- Recursive nature of the solution.
- Bottom-Up (solve smaller problems first)

## Thought Process

**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]}

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

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

}

}