Very Simple Java Solution with detail explanation (1ms, beats 96%)


  • 36
    K

    We take prices array as [5, 6, 2, 4, 8, 9, 5, 1, 5]
    In the given problem, we assume the first element as the stock with lowest price.
    Now we will traverse the array from left to right. So in the given array 5 is the stock we bought. So next element is 6. If we sell the stock at that price we will earn profit of $1.

    Prices:      [5, 6, 2, 4, 8, 9, 5, 1, 5]
    
    Profit:       Bought:5     Sell:6               Profit:$1             max profit=$1
    

    Now the next element is 2 which have lower price than the stock we bought previously which was 5. So if we buy this stock at price $2 and sells it in future then we will surely earn more profit than the stock we bought at price 5. So we bought stock at $2.

    Profit:      Bought:2     Sell:-              Profit:-                  max profit=$1
    

    Next element is 4 which has higher price than the stock we bought. So if we sell the stock at this price.

    Profit:      Bought:2     Sell:4              Profit:$2               max profit=$2
    

    Moving further, now the next stockprice is $8. We still have $2 stock we bought previously. If instead of selling it at price $4, if we sell it for $8 then the profit would be $6.

    Profit:      Bought:2     Sell:8              Profit:$6                max profit=$6
    

    Now next stock is of $9 which is also higher than the price we bought at ($2).

    Profit:      Bought:2     Sell:9              Profit:$7                max profit=$7
    

    Now the next stock is $5. If we sell at this price then we will earn profit of $3, but we already have a max profit of $7 because of our previous transaction.

    Profit:      Bought:2     Sell:5              Profit:$3                max profit=$7
    

    Now next stock price is $1 which is less than the stock we bought of $2. And if we buy this stock and sell it in future then obviously we will gain more profit. So the value of bought will become $1.

    Profit:      Bought:1     Sell:-              Profit:-                   max profit=$7
    

    Now next stock is of $5. So this price is higher than the stock we bought.

    Profit:      Bought:1     Sell:5              Profit:$4                max profit=$7
    

    But our maximum profit will be $7.

    public int maxProfit(int[] prices) {
                int ans=0;
                if(prices.length==0)
                {
                    return ans;
                }
                int bought=prices[0];                                
                for(int i=1;i<prices.length;i++)
                {
                    if(prices[i]>bought)
                    {
                        if(ans<(prices[i]-bought))
                        {
                            ans=prices[i]-bought;
                        }
                    }
                    else
                    {
                        bought=prices[i];
                    }
                }
         return ans;
    }

  • 0
    B

    Just for mark: time changes everything. it is not the fast, now it is 2ms , beat 64.79% on Aug 18, 2016


  • 0
    W

    I change
    if(ans<(prices[i]-bought))
    {
    ans=prices[i]-bought;
    }
    to
    ans=Math.max(ans,prices[i]-bought);
    and achieve 1ms beating 94%


  • -1
    W

    I don't think this algorithm is right.

    "Now the next element is 2 which have lower price than the stock we bought previously which was 5. So if we buy this stock at price $2 and sells it in future then we will surely earn more profit than the stock we bought at price 5. So we bought stock at $2."

    This argument doesn't hold if we change the second number (before 2) to a large number like 100.


  • 3
    U

    @wangjyee If the second number is changed to 100, then the max profit is 95 = 100-5 which is calculated in the first step. To move on, we will still choose to buy stock at $2 and see if there will be a price higher than 97 in the future. One can never buy a stock in the future and sell it in the past. So a large number before 2 will not affect the correctness of this algorithm.


  • 0
    M

    @Wenzhu_Zhao said in Very Simple Java Solution with detail explanation (1ms, beats 96%):

    ans<(prices[i]-bought

    can you explain why your method run faster by doing this change ?


  • 0
    X

    thanks!that helps a lot


  • 0
    J

    @xxxxzr said in Very Simple Java Solution with detail explanation (1ms, beats 96%):

    thanks! your explanation is easy to understand


  • 0
    S

    @keshavk thank you so much!! Your explanation is very clear!


Log in to reply
 

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