# 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.

• @raviteja2 has corrected

• class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1)
return 0;

``````    int sum = 0;
for(int i = 1; i < prices.size(); i++)
{
sum += (prices[i] - prices[i-1]) > 0 ? (prices[i] - prices[i-1]) : 0;
}
return sum;
}
``````

};

• This post is deleted!

• ``````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[i-1]>val) {
curr = prices[i-1]-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.length-1; d>=0; d--){
for(int a=0; a<actionNum; a++){
int nothing=profit[d+1][a];
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;
}
};

• ``````int maxProfit(int* prices, int pricesSize) {
if (pricesSize <= 1) {
return 0;
}

int profit = 0;
for (int i = 1; i < pricesSize; i++) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) {
profit += diff;
}
}

return profit;
}``````

• In approach 2, we need to check if prices is empty first, if so, return 0. Otherwise it will raise java.lang.ArrayIndexOutOfBoundsException: 0.

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

• So the idea is to take every uptrend movement. Should say it more clearly, I've seen a harder version of this problem--find the max biggest profit between valley and peak, i.e. the long transaction that makes most profit.

• Concise Java solution:

``````public int maxProfit(int[] prices) {
int profit = 0;
for(int i = 1;i<prices.length;i++) profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}``````

• my C++ solution:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
int profit=0;

``````    if(len==0||len==1)
return 0;

for(int i=0;i<len-1;i++)
{
if(prices[i]<prices[i+1])
profit+=prices[i+1]-prices[i];
}

return profit;
}
``````

};

• I think this problem looks same longest common increasing sequence as below to me. Am I missing anything?
public int findLengthOfLCIS(int[] nums) {
int res = 0, cnt = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0 || nums[i-1] < nums[i]) res = Math.max(res, ++cnt);
else cnt = 1;
}
return res;
}

• @ramsiddarth when i=0, you can not use nums[i-1]

• @mocha8lake agreed, but my question isnt this problem look similar to longest common increasing sequence where res can keep tracker of largest increasing sequence

• Why don't we start from i = 0, but from i = 1?

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