6. Best Time to Buy and Sell Stock

[bonfy]

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.

Example 1:

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.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Leetcode: 121. Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

[bonfy]

Case 1: 买卖一次

[bonfy]

解法1: 暴力

O(n²） Time Limit Exceeded

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 暴力

        max_pro = 0

        for i in range(1, len(prices)):
            for j in range(0, i):
                cur = prices[i] - prices[j]
                if cur > max_pro:
                    max_pro = cur

        return max_pro

[bonfy]

解法2: 遍历

• 记录最小 price 尝试 price[i] - min_price 与 max_pro 比较

O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        min_price = float('inf')
        max_profit = 0

        L = len(prices)
        for i in range(L):
            if prices[i] < min_price:
                min_price = prices[i]
            else:
                if prices[i] - min_price > max_profit:
                    max_profit = prices[i] - min_price

        return max_profit

[bonfy]

解法 3: DP

dp[i]

[bonfy]

Case 2: 买卖无数次

Leetcode: 122. Best Time to Buy and Sell Stock II - https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

[bonfy]

解法: Greedy

O(N) 遍历一次，每次只要后面的比前面的高 就可以买进前面的然后卖出

就和开挂一样

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        L = len(prices)
        if L <= 1:
            return 0
        max_pro = 0
        for i in range(1, L):
            if prices[i] - prices[i-1] > 0:
                max_pro += prices[i] - prices[i-1]
        return max_pro

[bonfy]

Case 3: 最多买卖 N 次 （比如 2次）