pic

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.

分析

题意是：现有一个整形数组，数组的第i个元素表示第i天某只股票的股价；在只允许一次交易（一次买，一次卖）的前提下，求最大收益。

理清这个题目，需要认识到一个隐含的条件：那就是卖在买后。剩下的就简单了，确定何时买，何时卖，得出（买，卖）的收益，从所有收益中得出最大收益。

    编程实现可以采用两种复杂度的算法：O(N*N)和O(N)
  • O(N*N)复杂度的算法是这样的，我们枚举出所有的买天和卖天，将所有的(买，卖)收益计算出来，求出最大收益。代码实现上，只需要两层for循环即可。这个算法思路清晰，实现简单，缺点确实复杂度高，O(N*N),在leetcode平台上出现了超时TIMEOUT错误，不能AC。
  • O(N)复杂度的算法稍微难理解一些，它是利用额外空间添加一个maxN数组(size就是天数)，maxN[pos]表示的含义是：第pos天到size天这size-pos天的最大股价，也就是我们可以卖出的最大价格。我们用这个max[pos]-prices[pos]就可以求出第pos天买入的最大收益，为什么？因为最大价格-买入价格得出的肯定是最大收益。然后我们遍历所有的maxN[pos]-prices[pos]找出最大收益的那一天。

Code

Code 1:O(N*N)算法(TIMEOUT)

class Solution {
public:
    /*
     * 通过股票的一次买和一次卖得到最大收益
     * 最简单的思路是枚举出所有的买的时间和卖的时间，得出每一个（买，卖）的收益来
     * 从所有的收益中找出最大的收益，复杂度为O(N*N)
     * 这个算法的实现在Leetcode平台上不能通过，TIMEOUT，说明需要小于O(N*N)的算法来实现。
     */
    int maxProfit(vector<int> &prices) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(prices.size() < 2)
        	return 0;
        int max = 0;
        for(int i = 0; i < prices.size() -1; i++)
        {
        	for(int j = i + 1; j < prices.size(); j++)
        	{
        		if(prices[i] - prices[j] > max)
        		{
        			max = prices[i] - prices[j];
        		} 
        	}
        }
        return max;
    }
};

Code 2:O(N)算法(Accepted)

class Solution {
    public:
        /* 
         * 之前用枚举所有（买，卖），得到最大收益的方法是O(N*N)，超时了
         * 我们考虑添加一个额外数组maxN用来存储最大卖价
         * 这个最大卖价是逆序推导的，从pos=prices.size()-1,开始，一只到0结束
         * maxN[pos]表示prices[pos]到prices[prices.size()-1]这几天的最大卖价，
		 * prices[pos]是这一天的买价，那么二者相减，就是收益
         * */
        int maxProfit(vector<int> &prices) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(prices.size() < 2)
                return 0;
            vector<int> maxN(prices.size(), 0);
            int max = 0;
			//注意是逆序，这是求出pos——prices.size()之间的最大卖价
            for(int pos = prices.size() - 1; pos >= 0; pos--)
            {
                max = max < prices[pos]?prices[pos]:max;
                maxN[pos] = max;
            }
            int ret = 0;
            for(int i = 0; i < prices.size(); i++)
            {
                int temp = maxN[i] - prices[i];
                if(temp > ret)
                    ret = temp;
            }
            return ret;
        }
};

pic