/*

Idea is based on dp, but really there is no point to keep track of the history.

Serveal fields is enough.

Say stock is:

3,2,6,5,0,3

Init the array to be 0

0,0,0,0,0,0

each index represents the max of whehter to buy or sell or hold on that day

day1:

0,0,0,0,0,0

day2:

it's a decreasing, not buy in

0,0,0,0,0,0

day3:

it's increasing from day 2, buy,

0,0,4,0,0,0

day4:

It's decrease, now have 2 options: if day3 did buy hold, if day3 didn't buy, use the max profit before day3

hold: 3

max profit before day 3: 0

choose hold

0,0,4,3,0,0

day5

Decrease again.

hold from day 4: - 2

max profit before day4: 4 on day3

choose the value at day3.

0,0,4,3,4,0

day6

increase. definately buy

0,0,4,3,4,7

Max is 7

*/

```
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length < 2) return 0;
int firstDay = 0;
int secondDay = 1;
int max = 0;
int secondMax = 0;
int profit_so_far = 0;
if(prices[secondDay] > prices[firstDay]){
max = prices[secondDay] - prices[firstDay];
secondMax = 0;
profit_so_far = max;
firstDay++;
secondDay++;
}
while(secondDay < prices.length){
int yesterday = profit_so_far;
if(prices[secondDay] > prices[firstDay]){
profit_so_far = Math.max(profit_so_far + prices[secondDay] - prices[firstDay], max);
}else{
profit_so_far = Math.max(profit_so_far + prices[secondDay] - prices[firstDay], secondMax);
}
if(profit_so_far > max){
max = profit_so_far;
}
secondMax = Math.max(secondMax, yesterday);
firstDay++;
secondDay++;
}
return max;
}
}```
```