Best Time to Buy and Sell Stock II

Solution

Note that the number of transactions is not limited.

Greedy

If today's price is higher than yesterday's, then transact. This may not guarantee the least number of transactions, but can for the maximum profit.

Complexity

time: $O(n)$
space: $O(1)$

def maxProfit(self, prices: List[int]) -> int:
    profit = 0
    for i in range(1, len(prices)):
        diff = prices[i] - prices[i-1]
        if diff > 0:
            profit += diff
    return profit

DP

dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。

def maxProfit(self, prices: List[int]) -> int:
    n = len(prices)
    dp = [[0 for _ in range(2)] for _ in range(n)]
    dp[0][0] = 0 # not buy
    dp[0][1] = -prices[0] # buy
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
    return dp[n-1][0] # definitely larger than dp[n-1][1]