BinarySearch 0457 Broker of Wall Street

Problem statement

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

Solution

Equal to Leetcode 0714. Best Time to Buy and Sell Stock with Transaction Fee.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, B, fee):
        if len(B) == 1: return 0
        n = len(B)
        
        dp, sp = [-float(inf)]*n, [0]*n

        for i in range(n-1):
            dp[i] = B[i+1] - B[i] + max(dp[i-1], sp[i-2] - fee)
            sp[i] = max(sp[i-1], dp[i])
             
        return sp[-2]