用 Python 买入和卖出股票 III 的最佳时机
pythonserver side programmingprogramming
假设我们有一个数组，其中第 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
对于 i 在 1 到 n 范围内
对于 j 在 1 到 m 范围内
如果 s[i] = t[j]，则
dp[i, j] := dp[i – 1, j – 1]
dp[i, j] := dp[i, j] + dp[i – 1, j]
return 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
