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

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

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

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

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

• @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.

• ans<(prices[i]-bought

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

• thanks!that helps a lot

• thanks! your explanation is easy to understand

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

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