123.md

123. Best time to buy and sell stock III

Dynamic Programming

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Solution:

$f(k,i) = max({f(k,i-1),prices[i]+f(k-1,j)-prices[j]})$

j in range (0,i)

$f(k,i) = max({f(k,i-1),prices[i]+max(f(k-1,j)-prices[j]}))$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)==0: return 0
        profit = [[0 for x in range(len(prices))] for y in range(0,3)]
        maxp = 0
        for i in range(1,3):
            temp = profit[i-1][0] - prices[0]
            for j in range(1, len(prices)):
                profit[i][j] = max(profit[i][j-1],prices[j]+temp)
                temp = max(temp,profit[i-1][j]-prices[j])
                maxp = max(maxp,profit[i][j])
        return maxp

        

188. Best Time to Buy and Sell Stock IV

Solution:

• dp[i, j] represents the max profit up until prices[j] using at most i transactions.

• dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] } = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))

• dp[0, j] = 0; 0 transactions makes 0 profit

• dp[i, 0] = 0; if there is only one price data point you can't make any transaction.

  Dynamic programming

  class Solution:
      def maxProfit(self, k: int, prices: List[int]) -> int:
          n = len(prices)
          if n==0 or k==0:
              return 0
          dplist = [[0 for x in range(n)] for x in range(k+1)]
          for i in range(1,k+1):
              for j in range(1,n):
                  tempmax = dplist[0][0]-prices[0]
                  for m in range(0,j):
                      tempmax = max(dplist[i-1][m]-prices[m],tempmax)
                  dplist[i][j] = max(dplist[i][j-1],prices[j]+tempmax)
          return dplist[k][n-1]

  Memory exceed 👇

  if (k >=  n/2):
      maxPro = 0
      for i in range(1,n):
          if prices[i] > prices[i-1]:
              maxPro += prices[i] - prices[i-1]
      return maxPro;