[leetcode]121.122. Best Time to

题目

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.

// 121
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

// 122
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

解析

题目121 和 122 的区别在于， 121指定只可以做一次交易， 而122 可以做出任意次交易。

• 针对121， 只需要遍历一次数组，维持一个变量记录最小值，另一个变量记录这个最小值与它后面的值的最大差值，遍历结束并最终返回即可。

-针对122，因为可以多次交易，所以只需要找到所有数组中连续的增序序列最大最小值的差值即可，并把所有差值加和。

代码

121：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        min = prices[0]
        max_profit = 0
        for i in prices[1:]:
            if i > min :
                max_profit = max(i - min, max_profit) 
            else:
                min = i
        return max_profit

122：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if  not prices:
            return 0
        buyprice = float('inf')
        cur_profit = 0
        max_profit = 0
        
        for i in prices:
            cur_profit = i - buyprice
            max_profit = max(max_profit + cur_profit, max_profit)
            buyprice = i
        return max_profit