[DP][Divide and Conquer] Maximum Subarray

1. Example

Find  the contiguous subarray with the largest sum

s= [-2,1,-3,4,-1,2,1,-5,4]
the contiguous subarray [4,-1,2,1]
Return the largest sum 6

2. Implementation
Q1: sum => sorted?
A1: the answer require contiguous subarray, so we cannot break the original order
Q1: contiguous + maximum => DP
A1: DP[i] = max(DP[i-1] + s[i] , s[i]) ,since array may include negative number, so there is a chance current element value is greater than previous sum.
However, there is a a possibility DP[i-1] + s[i] < DP[i].
DP[i]  = max( DP[i-1]+s[i],s[i]), DP[i] the maximum sum including  i element
max= max(max, DP[i])
Q1: DP ?
A1: when there is a sense to pick up from start or pick up from anywhere and go on
FOLLOW UP: maximum product subarray
product have an chance to Negative* Negative become the largest
keep negative as a tempLastProduct and check every time
Q1: s=[-2,1,-3,4,-1,2,1,-5,4]
-2= -2            
-1=-2,1
-4=-2,1,-3
0=-2,1,-3,4
..
1=1
-2=1,-3
2=1,-3,4
..
-3 X
4
res[i] = the largest sum till i
i = 0 res[0] = -2
i =1 res[1] = max(res[0], 1, res[0]+1)

 // NOTE:
int local = num[0]; // NOTE: local keep tracking accumulated value or pervious value, but max just keep max which could be the last few element like first element, e.g., 10, -3,-2,-1 max =10, local = 10+-3+-2+-1

local = Math.max(local+nums[i], nums[i]); 

public int maxSubArray( int[] nums )
{
       // validate the input
       if (nums == null || nums.length ==0)
       {
           return Integer.MIN_VALUE;
       }



      
       // NOTE: don't have to keep an array to record each maximum so far, we just need the maximum value
       int global = nums[0];
       // NOTE: 
       int local = num[0];
       for (int i = 1; i < nums.length; i++)
       {
            //int local = Math.max(max+nums[i], nums[i]);
            // NOTE: local keep tracking accumulated value or pervious value, but max just keep max which could be the last few element like first element, e.g., 10, -3,-2,-1 max =10, local = 10+-3+-2+-1
            local = Math.max(local+nums[i], nums[i]);
            global = Math.max(global, local);
       }






       return global;



}
[-2,1,-3,4]
i =1 
-2+1,1 => 1 
1,-2 =>1 max

i=2
1+-3, -3=>-2
1,-3=>1 max

i=3
1+4, 4=>5
1,5 =>5

3. Similar Ones
(M)Best Time to Buy and Sell Stock
(M)Maximum Product Subarray