leetcode: Best Time to Buy and Sell Stock

问题描述：

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.

原问题链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

问题分析

　　这个问题看起来很简单，不过还是有一些细节需要注意的。首先，这里给出的数组值是一组股票价格的值，对于用户来说只能有一次交易的机会，这意味着用户只能在里面选择某个点买，而在某个点卖。而这里买的点肯定在数组的前面，而卖的点肯定在这个买点的后面。

　　相对这个问题来说，我们需要找到一个对于数组后面的元素和前面元素的差值，并且这个差值最大的值就是我们想要的结果。当然，如果后面的差值也可能小于等于零，在这种情况下，我们返回结果0。

　　那么，该怎么来找这个元素呢？我们首先取数组里的第一个元素假定为最小的值，然后从开始向后遍历数组。每次碰到一个元素的时候就和当前假定最小的元素比较，设定最小值min为比较小的那个。然后我们再计算当前值和我们当前得到的最小值min的差，取这些差值中最大的那个。这样我们将得到最终的结果。这里还有一些特殊情况要考虑，比如说数组的长度小于2的时候，没法实现买入和卖出，所以应该返回结果0。

　　详细的代码实现如下：

 

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2) return 0;
        int low = prices[0], result = 0;
        for(int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);
            result = Math.max(result, prices[i] - low);
        }
        return result;
    }
}