用Python买卖股票III的最佳时间

假设我们有一个数组，第i个元素代表第i天给定股票的价格。我们必须设计一种算法来找到最大的利润。我们最多可以完成两笔交易。因此，如果给定价格为[3,3,5,0,1,3,1,4]，则结果将为6，因为我们将在第4天买入（价格0），然后在第6天卖出，（价格3），则利润为3 – 0 =3。现在，但在第7天（价格1），并在第8天卖出（价格4），因此利润为4 – 1 = 3。

为了解决这个问题，我们将遵循以下步骤-

• n：= s的大小，m：= t的大小。通过在空格之前连接s和t来更新它们

• 制作一个大小为（n + 1）x（m + 1）的矩阵

• 设置dp [0，0]：= 1，然后为所有行的第0列设置1，放入1

• 对于我在1到n范围内

• 如果s [i] = t [j]，则

• dp [i，j]：= dp [i，j] + dp [i – 1，j]

• dp [i，j]：= dp [i – 1，j – 1]

• 对于1到m范围内的j

• 返回dp [n，m]

示例

让我们看下面的实现以更好地理解-

class Solution(object):
   def maxProfit(self, p):
      if not p:
         return 0
      n = len(p)
      dp = [0 for i in range(n)]
      ans = 0
      xmin = p[0]
      for i in range(1,n):
         xmin = min(xmin,p[i])
         dp[i] = max(dp[i],p[i]-xmin)
         ans = max(ans,dp[i])
      xmax = [0 for i in range(n)]
      xmax[-1] =p[-1]
      tempp = 0
      for i in range(n-2,-1,-1):
         xmax[i] = max(xmax[i+1],p[i])
      xmin = [p[-1],n]
      for i in range(n-2,-1,-1):
         tempp = max(tempp,xmax[i+1]-p[i+1])
         ans = max(ans,dp[i]+tempp)
      return ans
ob = Solution()print(ob.maxProfit([3,3,5,0,1,3,1,4]))

输入值

[3,3,5,0,1,3,1,4]

输出结果

6