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

Log in to reply
 

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