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]; } }

C++ solution:
This is much easier than I thought:
class Solution {
public:
int maxProfit(vector<int>& prices)
{
int maxProfit = 0;
for (unsigned i = 0; i < prices.size(); ++i)
{
if ((i+1) < prices.size())
{
maxProfit += (prices[i+1] < prices[i]) ? 0 : prices[i+1]  prices[i];
}
}
return maxProfit;
}
};

in fact you have just to prove that : [a1........an] is a
Increment sequence,and the an a1 =(a2a1)+(a3a2)+...(anan1) and you must remove (a3a2) ,because you can not both add(a2a1)+(a3a2) at the same time, so by ana1 you can get the max profit, of course the condition is that the sequence is incresing so you must let(price[i]>price[i1]);