买卖股票的最佳时机——Python 中的另一种方法

Question

问题 - 假设您有一个数组，其ith元素是给定股票在 day 的价格i。

如果您最多只被允许完成一笔交易（即买入一股并卖出一股股票），请设计一种算法来找到最大利润。

请注意，您不能在购买股票之前出售股票。

示例1：

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

示例2：

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

我相信这个问题可以使用动态编程来解决，在简单地继续解决方案之前，我尝试使用我自己的方法来解决这个问题。我确实检查了蛮力算法并意识到我的方法与蛮力并不相似

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

这是我的方法

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res=0
        if not prices:
            return 0
        idx=prices.index(min(prices))
        value=min(prices)
        try:
            for i in range (idx+1,len(prices)):
                res=max(res,prices[i]-value)
        except IndexError :
            return 0
        return res    

我的代码通过了示例测试用例和 143/200 个用例，但在这一用例中失败了。

Input: [2,4,1]
Output: 0
Expected: 2

我怎样才能改进我的代码？我怎样才能使这种方法发挥作用？或者如果这种方法完全错误，请详细说明。

我相信我的方法的时间复杂度比暴力破解要好，因此，要努力使这段代码工作；稍后再看看动态编程方法

Answer 1

def max_profit(prices):
    if not prices:
        return 0

    max_prof = 0
    min_price = prices[0]

    for i in range(1, len(prices)):
        if prices[i] < min_price:
            min_price = prices[i]
        max_prof = max(max_prof, prices[i] - min_price)
    return max_prof

输出：

print(max_profit([1, 2, 3, 4, 5]))
print(max_profit([5, 4, 3, 2, 1]))
print(max_profit([3, 1, 2, 4, 5]))
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
print(max_profit([2, 4, 1]))
4
0
4
5
0
2