Best Time to Buy and Sell Stock II


  • 0

    Click here to see the full article post


  • 0
    R

    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.


  • 0
    W

    @raviteja2 has corrected


  • 0
    O

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

    };


  • 0
    S
    This post is deleted!

  • 0
    S
    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;
        }
    }
    

  • 0
    H

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

  • 0
    R

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


  • 0
    H
    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;
    }

  • 0
    C

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


  • 0
    S

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


  • 0
    S

    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.


Log in to reply
 

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