用 Python 买卖股票的最佳时机

pythonserver side programmingprogramming更新于 2025/10/26 23:08:17

假设我们有一个数组 A，这里 A[i] 表示第 i 天某只股票的价格。我们必须找到最大的利润。我们最多可以完成一笔交易。(交易意味着买卖股票)。但我们必须记住，我们可能不能同时进行多笔交易。所以我们必须先卖掉股票，然后再买入新股票。

假设数组是 A = [7, 1, 5, 3, 6, 4]，那么结果将是 5。我们可以看到，如果我们在第 2 天(索引 1)买入，那么它将以 1 作为买入价格。那么如果我们在第 5 天卖出，利润将是 6 – 1 = 5。

要解决这个问题，请按照以下步骤 −

创建两个大小与 A 相同的数组 leftMin 和 rightMax，并用 0 填充它们
leftMin[0] = A[0]
对于范围从 1 到 A 的长度 – 1 的 i，leftMin[i] = leftMin[i – 1] 和 A[i] 的最小值
rightMax[n-1] = A[n – 1]
对于范围从 A 的长度 – 1 到 1 的 i，rightMax[i] = rightMax[i + 1] 和 A[i] 的最大值
设置答案 := 0
对于范围从 0 到 A 的长度 – 1，答案:= 答案和 rightMax[i + 1] 的最大值 – leftMin[i]
返回答案

让我们看看实现以便更好地理解

示例

class Solution(object):
   def maxProfit(self, prices):
      """
      :type prices: List[int]
      :rtype: int
      """
      if not prices:
         return 0
      leftMin,rightMax = [0 for i in range(len(prices))],[0 for i in range(len(prices))]
      leftMin[0] = prices[0]
      for i in range(1,len(prices)):
         leftMin[i] = min(leftMin[i-1],prices[i])
      #print(leftMin)
      rightMax[-1]= prices[-1]
      for i in range(len(prices)-2,-1,-1):
         rightMax[i] = max(rightMax[i+1],prices[i])
      #print(rightMax)
      ans = 0
      for i in range(len(prices)-1):
         ans = max(ans,rightMax[i+1]-leftMin[i])
      return ans
ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))