BinarySearch 0441 Bear of Wall Street

Problem statement

https://binarysearch.com/problems/Bear-of-Wall-Street/

Solution

Equal to Leetcode 0309. Best Time to Buy and Sell Stock with Cooldown.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, prices):
        n = len(prices)
        if n <= 1: return 0
        
        diff = [prices[i+1] - prices[i] for i in range(n-1)]
        dp, dp_max = [0]*(n + 1), [0]*(n + 1)
        for i in range(n-1):
            dp[i] = diff[i] + max(dp_max[i-3], dp[i-1])
            dp_max[i] = max(dp_max[i-1], dp[i])
            
        return dp_max[-3]