Leetcode 121 Best Time to Buy and Sell Stock

题目原文

Say you have an array for which the i^th 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.

转自：here

题意分析

本题是一个简单的求最优解问题，只能买卖一次股票，求最大收益，当卖的时候的价格比买的时候高，收益为0。

解法分析

本题采用动态规划方法求解。如果用暴力方法，显而易见算法复杂度为O(n^2)，所以一般用动态规划该方法复杂度变为o(n)，只有一个for循环，也就是通过遍历一次原序列就能得到解。首先分析最优子结构，令从左开始的一个子序列中最小元素为a，下一个元素为b，如果b比a小，则算上b后的序列的最小元素就是b，否则仍是a；如果b比a大，则求其差值，与Pro比较，如果差值大于pro，则修改pro的值，否则pro的值不变。这是一个简单的自底向上的动态规划问题。C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0||n==1)
            return 0;
        int pro=0,min=prices[0],i,temp;
        for(i=1;i<=n-1;i++){
            if(prices[i]>min){
                temp=prices[i]-min;
                if(temp>pro)
                    pro=temp;
            }
            else
                min=prices[i];
        }
        return pro;   
    }
};

由于只有一个for循环，所以复杂度为O(n)，注意对空输入和只有一个元素的输入的处理，都应输出0。

Another way, from here


这道题求进行一次交易能得到的最大利润。如果用brute force的解法就是对每组交易都看一下利润，取其中最大的，总用有n*(n-1)/2个可能交易，所以复杂度是O(n^2)。
很容易感觉出来这是动态规划的题目，其实跟Maximum Subarray非常类似，用“局部最优和全局最优解法”。思路是维护两个变量，一个是到目前为止最好的交易，另一个是在当前一天卖出的最佳交易（也就是局部最优）。递推式是local[i+1]=max(local[i]+prices[i+1]-price[i],0), global[i+1]=max(local[i+1],global[i])。这样一次扫描就可以得到结果，时间复杂度是O(n)。而空间只需要两个变量，即O(1)。代码如下：

public int maxProfit(int[] prices) {
    if(prices==null || prices.length==0)
        return 0;
    int local = 0;
    int global = 0;
    for(int i=0;i<prices.length-1;i++)
    {
        local = Math.max(local+prices[i+1]-prices[i],0);
        global = Math.max(local, global);
    }
    return global;
}

这种题目的解法非常经典，不过是比较简单的动态规划。这道题目还有两个变体，Best Time to Buy and Sell Stock II和Best Time to Buy and Sell Stock III，虽然题目要求比较像，但是思路却变化比较大，Best Time to Buy and Sell Stock II可以交易无穷多次，思路还是比较不一样，而Best Time to Buy and Sell Stock III则限定这道题交易两次，其实还可以general到限定交易k次，会在这道题目中仔细讲解，有兴趣的朋友可以看看哈。