Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]

Output: 0

In this case, no transaction is done, i.e. max profit = 0.

解法一：

先看@keshavk 的解析和代码

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

             if(prices.length==)

             {

                 return ans;

             }

             int bought=prices[];

             for(int i=;i<prices.length;i++)

             {

                 if(prices[i]>bought)

                 {

                     if(ans<(prices[i]-bought))

                     {

                         ans=prices[i]-bought;

                     }

                 }

                 else

                 {

                     bought=prices[i];

                 }

             }

      return ans;

 }

解法二：

结合上面解法一的思路，重新简化代码

 class Solution {

 public:

     int maxProfit(vector<int>& prices) {

         int min_value = INT_MAX;

         int max_value = ;

         for (int i = ; i < prices.size(); ++i) {

             min_value = min(min_value, prices[i]);

             max_value = max(max_value, prices[i] - min_value);

         }

         return max_value;

     }

 };

写的过程中参考了@linjian2015 的代码

解法三：

public int maxProfit(int[] prices) {

    int maxCur = 0, maxSoFar = 0;

    for(int i = 1; i < prices.length; i++) {

        maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);

        maxSoFar = Math.max(maxCur, maxSoFar);

    }

    return maxSoFar;

}

参考@jaqenhgar 的代码

The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

*maxCur = current maximum value

*maxSoFar = maximum value found so far

关于 Kadane's Algorithm 说明如下：

 def max_subarray(A):

     max_ending_here = max_so_far = A[0]

     for x in A[1:]:

         max_ending_here = max(x, max_ending_here + x)

         max_so_far = max(max_so_far, max_ending_here)

     return max_so_far

参考自：https://en.wikipedia.org/wiki/Maximum_subarray_problem