Sharing my simple and clear C++ solution


  • 197
    Z
    int maxProfit(vector<int> &prices) {
        int maxPro = 0;
        int minPrice = INT_MAX;
        for(int i = 0; i < prices.size(); i++){
            minPrice = min(minPrice, prices[i]);
            maxPro = max(maxPro, prices[i] - minPrice);
        }
        return maxPro;
    }
    

    minPrice is the minimum price from day 0 to day i. And maxPro is the maximum profit we can get from day 0 to day i.

    How to get maxPro? Just get the larger one between current maxPro and prices[i] - minPrice.


  • 2
    Z

    good I have the same idea


  • 1

    I really love this solution: clear and short.


  • 0
    A

    my answer ,define more maxmum
    int maxProfit(vector<int>& prices)
    {
    int iLength = prices.size();
    int iMaxFit = 0, iMin = INT_MAX, iMax = INT_MAX;
    for (int iIndex = 0; iIndex < iLength; iIndex++)
    {
    if (prices[iIndex] < iMin)
    {
    iMin = prices[iIndex];
    iMax = iMin;
    }
    if (prices[iIndex] > iMax)
    {
    iMax = prices[iIndex];
    if (iMax - iMin > iMaxFit)
    { iMaxFit = iMax - iMin; }
    }
    }
    return iMaxFit;
    }


  • 46

    Very nice solution! But it still can be optimized. We only need to calculate either maxProfit or minPrice not both in every loop. Running time can be dropped by 33% percent.

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2) return 0;      
        int maxProfit = 0, minPrice = prices[0];
        
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);       
            } else {
                 minPrice = Math.min(minPrice, prices[i]);
            }
        }
    
        return maxProfit;
    }

  • 0

    Don't down vote me. Haha. I've experimented and the time dramatically reduced.
    We don't need to calculate max in every loop.


  • 1
    Z

    If you use this method, take a look at Buy and Sell Stock III
    similar solution: https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1


  • 0
    T

    I think comparing prices[i] and prices[i-1] also costs time.


  • 0
    This post is deleted!

  • 0

    making a graph describing price course based on day can help us understand it easly!


  • 0
    F

    I have implemented one place different by changing the order of updating the min-price and the max profit, then i GOT it wrong, I find the corner cases is important to deal with.


  • 2
    M

    Improve it more better

    int maxProfit(int* prices, int pricesSize) {
    if(!prices || pricesSize < 2) return 0;
    int maxProfit = 0, minPrice = prices[0];

    for(int i = 1; i < pricesSize; i++) {
        if(prices[i] > minPrice) {
            maxProfit = max(maxProfit, prices[i] - minPrice);       
        } else {
            minPrice = min(minPrice, prices[i]);
        }
    }
    
    return maxProfit;    
    

    }

    @yavinci said in Sharing my simple and clear C++ solution:

    Very nice solution! But it still can be optimized. We only need to calculate either maxProfit or minPrice not both in every loop. Running time can be dropped by 33% percent.

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2) return 0;      
        int maxProfit = 0, minPrice = prices[0];
        
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);       
            } else {
                 minPrice = Math.min(minPrice, prices[i]);
            }
        }
    
        return maxProfit;
    }

  • 0

    A little slow, but very clear and short after getting rid of the 'If'. Thanks for sharing!


  • 0
    Y

    I think this is not the actual DP, Although I had the same idea.


  • 0
    K

    my version of solution, very similar idea

    public class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null) {
                return 0;
            }
            int min = Integer.MAX_VALUE;
            int profit = 0;
            for (int i = 0; i < prices.length; i++) {
                if (prices[i] < min) {
                    min = prices[i];
                } else {
                    profit = Math.max(profit, prices[i] - min);
                }
            }
            return profit;
        }
    }
    

  • 1
    H

    @yavinci said in Sharing my simple and clear C++ solution:

    if(prices[i] > prices[i - 1]) {

    However, instead of spending time calculate the MAX, you CPU needs more time checking whether prices[i] > prices[i - 1]). Thus, I don't think there will be much effect on run time.


  • 0
    P

    @zxyperfect Nice idea.

    Python implementation

    class Solution(object):
    def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """

        profit = 0 
        min_price = 2**31
    
        for x in prices:
            min_price = min(min_price, x)
            profit = max(profit, x-min_price)
            
        return profit

  • 0
    Y

    I use the same idea, but I use ternary operator instead of min and max function, that will be a little bit faster.


  • 0
    W

    The solution very clean and nice! The baisic idea is to continuously update minPrice and maxPro.


  • 0
    Z

    clear and easy to understand


Log in to reply
 

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