Q121 Best Time to Buy and Sell S

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.

解题思路：

这题第一反应和最大子段和问题 Q53 Maximum Subarray 差不多，因此可以用动态规划求解。

用一个列表记录当前累积的最大利润。如果当前值比下一个值小，则用下一个值减去当前值作为最大利润，然后当前值下标不变，下一个值往后滑动一位继续比较。如果当前值比后面的某个值大，则最大利润置为0，当前值下标变为后面那个值的下标。一次遍历，返回利润列表中的最大值。时间复杂度为 O(n)。

Python实现：

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        li = [0]  # 当前累积的最大利润
        i = 0; j = 1
        while j < len(prices):
            if prices[i] >= prices[j]:
                li.append(0)
                i = j
            else:
                li.append(prices[j] - prices[i])
            j += 1
        return max(li)

a = [7,2,5,3,6,4,1,5,6,4,0]
b = Solution()
print(b.maxProfit(a)) # 5 # 1元的时候买入，6元的时候卖出