博文中会简要介绍Leetcode P0121题目分析及解题思路。

“Best Time to Buy and Sell Stock”是一道比较简单的题目，其原型题是p0188，是一道比较难同时很经典的题目，而这道题是它的简化版。

一般有两种思路，一种是用动态规划的思想，从右到左扫一遍数组，每次记录当前价格右边的最大值；另一种是用双指针的思想，维护两个变量，一个是最小值，另一个是该最小值右边的最大值。

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

双指针的思路不再赘述，Java代码实现了双指针解法。动态规划的方法比较简单，递推表达式如下：

令rightMax是当前指针右边的最大值，

rightMax = max(rightMax, p[i])
其中i是当前指针位置，从右到左。

profit = max(profit, rightMax-p[i])
通过上式即可得到该区间内的利润最大值。

以下是Java的题解代码实现。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;
        
        int min = prices[0], max = prices[0], profit = 0;
        boolean isValid = true;
        for (int day=1; day<prices.length; ++day) {
            if (prices[day] < min) {
                min = prices[day];
                max = min;
            }
            else {
                max = Math.max(max, prices[day]);
                profit = Math.max(profit, max-min);
            }
        }
        
        return profit;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1)
            return 0;
        
        int days = prices.size()-1, rightMax = prices[days], profit = 0;
        // DP
        for (int day=days-1; day>=0; --day) {
            rightMax = max(rightMax, prices[day]);
            profit = max(profit, rightMax-prices[day]);
        }
        
        return profit;
    }
};