# Java Step by step with example, tell you why this could be solved without DP

• /*
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
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;

}
}`````````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.