python代码不能在数组中工作。

Question

这是一个算法问题，其主题是:买卖股票的最佳时机

假设您有一个数组，其中ith元素是第一天给定股票的价格。如果只允许您完成最多一笔交易(即购买一笔股票并出售一股股票)，则设计一种算法来寻找最大利润。

*示例1：输入: 7，1，5，3，6，4输出:5

麦克斯。差额= 6-1 =5(而不是7-1 = 6，因为销售价格需要大于买入价格).*

*示例2：输入: 7，6，4，3，1输出:0

在这种情况下，不进行任何事务，即最大利润= 0.*

我用蟒蛇算出来的。守则如下：

class Solution(object):
def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    i=Max=0
    if not prices:
        return 0
    while i+1 <= len(prices)-1:
        j=i+1
        while j < len(prices):
            if prices[i] < prices[j]:
                Max = max(Max, prices[j] - prices[i])
                j+=1
            j+=1
        i+=1
    return Max

然而，系统告诉我我错了：返错

试过了但我不知道错误在哪里..。有人能帮忙吗？非常感谢!

Answer 1

干得好！虽然可以对代码进行一些改进，但让我们关注导致代码返回错误结果的一个错误：

    Max = max(Max, prices[j] - prices[i])
    j+=1
j+=1

这是双j += 1。无论何时更改最大值，j都会增加两次，从而跳过一些比较。

删除j += 1中的if-branch，您将得到输入向量的正确结果：

    Max = max(Max, prices[j] - prices[i])
j+=1

如果有兴趣，以下是一些改进编码风格的建议：

• while i+1 <= len(prices)-1:添加1并使用<=是多余的。while i < len(prices)-1:会稍微干净一些。
• For循环比while循环更容易阅读，性能也略好一些。当只有一个计数器需要增加时，使用它们： 对于i在范围内(len(价格))：对于j在范围内(i，len(价格))：如果价格i< pricesj: Max =Max(最大价格)
• 在这种情况下不需要使用类。

Answer 2

据我所知，我认为您必须将问题改写并调整为代码。我根据这些例子和预期结果提出的意见如下：

• 购买价格在输入列表中，必须识别。
• 销售价格也在输入列表中，并且必须被识别。
• 买价必须低于卖价。
• 利润是产出，因此是buying-selling。

现在，将其转换为一个算法：

尝试1(在某些情况下错误-见注释)

1. 在清单中找到最小值--这是我们的买入价格。
2. 在“同一天或晚些时候”的列表中找到最大值。该指数与买入价格指数相同或较大。

代码(单个可执行文件--如果需要的话，您需要使它成为一个函数)：

#!/usr/bin/env python

import sys

# Not part of the algorithm: converts first argument to a list of integers
prices = map(int, sys.argv[1].split(","))

# Find the best buying price
buy = min(prices)
# Find the best buying time/index
buyidx = prices.index(buy)

# Now the best selling price is the next maximum
sell = max(prices[buyidx:])

print(" Input: %s" % str(prices))
print("Output: %d" % (sell-buy))

示例：

$ /tmp/stock.py 1,2,4
 Input: [1, 2, 4]
Output: 3
$ /tmp/stock.py 7,1,5,3,6,4
 Input: [7, 1, 5, 3, 6, 4]
Output: 5

$ /tmp/stock.py 1,2,3,4,5
 Input: [1, 2, 3, 4, 5]
Output: 4
$ /tmp/stock.py 4,3,2
 Input: [4, 3, 2]
Output: 0
$ /tmp/stock.py 4,3,1
 Input: [4, 3, 1]
Output: 0
$ /tmp/stock.py 4,3,5
 Input: [4, 3, 5]
Output: 2

基于@kazemakase输入的尝试2

1. 购买价格在清单上，但不一定是最低价值。它是价值最大化的利润！
2. 每一天，计算一下如果我们购买当天的股票，我们的利润会是什么？？卖价是指数大于今天的最大值。
3. (@kazemakase)循环有时是不可避免的

守则：

#!/usr/bin/env python

import sys

prices = map(int, sys.argv[1].split(","))

# For every day
buy_final = 0
sell_final = 0
max_profit = 0
for (buyindex, buy) in enumerate(prices):
    sell = max(prices[buyindex:])
    profit = sell - buy
    if profit > max_profit:
        max_profit = profit
        buy_final = buy
        sell_final = sell

print(" Input: %s" % str(prices))
print("Output: %d" % (sell_final-buy_final))

结果：

$ /tmp/stock.py 7,1,5,3,6,4
 Input: [7, 1, 5, 3, 6, 4]
Output: 5
$ /tmp/stock.py 1,2,4
 Input: [1, 2, 4]
Output: 3
$ /tmp/stock.py 3,6,1,2
 Input: [3, 6, 1, 2]
Output: 3

如果你需要更多的澄清，或者我的假设是错误的，请告诉我。

Answer 3

class Solution(object):
def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    i=Max=0
    if not prices:
        return 0
    while i+1 <= len(prices)-1:
        j=i+1
        while j < len(prices):
            if prices[i] < prices[j]:
                Max = max(Max, prices[j] - prices[i])
                j+=1 // <---THIS IS BUGGY LINE
            j+=1
        i+=1
    return Max

如果执行be行，j将总共执行+= 2，这可能会跳过数组中的一些值，成为price[j]。

在您的例子中，当i = 0, j = 1时，您将得到Max = price[1] - price[0] = 1。

然后j将+= 2，这是没有限制的，所以你永远不会得到Max = price[2] - price[0] = 3。

然后，当i = 1, j = 2时，您将得到Max = price[2] - price[1] = 2，这是您的最终结果