Python 中股票最佳买卖时机

假设我们有一个数组 A，其中 A[i] 表示某一天的股票价格。我们需要找到最大利润。我们最多可以完成一笔交易。（交易意味着买卖股票）。但我们必须记住，我们不能同时进行多笔交易。因此，我们必须在购买新股票之前卖出股票。

假设数组如下：A = [7, 1, 5, 3, 6, 4]，则结果为 5。我们可以看到，如果我们在第 2 天（索引 1）购买，则购买价格为 1。然后，如果我们在第 5 天卖出，利润将为 6 – 1 = 5。

要解决此问题，请按照以下步骤操作：

  • 创建两个与 A 大小相同的数组 leftMin 和 rightMax，并用 0 填充它们
  • leftMin[0] = A[0]
  • 对于 i 从 1 到 A 的长度 – 1，leftMin[i] = leftMin[i – 1] 和 A[i] 的最小值
  • rightMax[n-1] = A[n – 1]
  • 对于 i 从 A 的长度 – 1 到 1，rightMax[i] = rightMax[i + 1] 和 A[i] 的最大值
  • 设置答案 := 0
  • 对于 i 从 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]))

输入

prices = [7,2,5,8,6,3,1,4,5,4,7]

输出

6

更新于： 2020-04-28

417 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告