[DP] Best Time to Buy and Sell Stock

1. Example

s is array of price at each day
s = [$10, $50, $60, $20, $45, $100]
Find the maximum profit?
Only one transaction

2. Implementation
two nested for loop to compare i=0 - len-1 j = i+1 - len-1
Q1: only one transaction
A1: fins the lowest point and highest point but may not in chronological order, so do transaction in chronological order and compute the maximum
Q1: how to accumulate ?
A1: suppose $0 $10 $40 we want $ 0 and $40 so we can accumulate two section $10-$0 + ($40 -$10) to get .
A1: suppose $10 $0 $40 anyone after  has the lowest value (like $0), we take it to replace the previous value ()
DP
so far the maximum profit
DP[i] = MAX(     DP[i-1] + (prices[i]-prices[i-1]) ,  (prices[i]-prices[i-1])     )
//NOTE:

local = Math.max(local+prices[i+1] - prices[i],prices[i+1] - prices[i]);

// Time:O(n) over array, Space:O(1) local global variables
public int maxProfit(int[] prices)
{

     // validate the input
     if (prices == null || prices.length ==0)
     {
          return 0;
     }



     int global = 0;
     int local = 0;
     for (int i = 0 ; i <  prices.length -1; i++ )
     {
          //X int local = prices[i+1] - prices[i]  ([i+1]-[i],0)
          // NOTE: 
          local = Math.max(local+prices[i+1] - prices[i],prices[i+1] - prices[i]);
          //X global = Math.max(local+global, local); // if local is negative, it will be ruled out
         global = Math.max(global, local);
     }
}

[$10, $0, $50]
i = 0 local =-10, global = 0
i=1   local = 50, global =max(0+50,50) =50

[$0, $10, %40]
i = 0 local 10. global =10
i=1 local =30 global =max(30+10, 30) = 40

[%50,$30,$0]
i= 0 local -20 global 0
i=2 local -30 global max(0,-30) = 0

3. Similar ones
NOTE: maximum, continuous
Maximum Subarray
Best Time to Buy and Sell Stock II, III, IV