Best Time to Buy and Sell Stock II


This solutions is wrong for the example 7, 1, 5, 3, 6, 4 the maximum profit made is buy on 1 sell on 5 profit =4 + buy on 3 and sell on 6 profit is 3 => total max profit = 7 but according to the code its 5. if we take another example of 1,2,1,100 the max profit is 100 buy on 1 sell on 2 buy on 1 sell on 100 not 99.


public class Solution { public int maxProfit(int[] prices) { int curr=0, sum=0; if(prices.length<2) return 0; int low=prices[0]; for(int i=1; i<prices.length+1;i++){ int val = i==prices.length? 0:prices[i]; if(prices[i1]>val) { curr = prices[i1]low; low = val; if(curr>0) sum+=curr; } } return sum; } }

DP solution:
Time complexity: O(n)
Space complexity: O(n)// 0 is sell, 1 is buy // For each day, I have three choices: buy, sell or do nothing. // int maxProfit(int day, int nextAction) > int p(d, a) // p(d, a)= //if a==1 max{p(d+1, 0)prices[d], nothing} //if a==0&&d==0 nothing //if a==0&&d!=0 max{p(d+1, 1)+prices[d], nothing} //note that nothing=p(d+1, a) public class Solution { public int maxProfit(int[] prices) { int actionNum=2; int[][] profit=new int[prices.length+1][actionNum]; profit[prices.length][0]=0; profit[prices.length][1]=0; for(int d=prices.length1; d>=0; d){ for(int a=0; a<actionNum; a++){ int nothing=profit[d+1][a]; if(a==1){//buy profit[d][a]=Math.max(profit[d+1][0]prices[d], nothing); }else{//a==0, which means to sell. if(d==0){// I can't sell in the first day profit[d][a]=nothing; }else{ profit[d][a]=Math.max(profit[d+1][1]+prices[d], nothing); } } } } return profit[0][1]; } }