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

Question

QUESTION-假设您有一个数组，其ith元素是第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

Answer 2

对于这个问题，最有效的算法是 O(N( 时间和 O(1( 空间，它不能再高效了，因为在这里我们必须至少访问每个元素一次：

class Solution:
def maxProfit(self, prices):
if not prices:
return 0
max_price = 0
min_price = float('inf')
for i in range(len(prices)):
if prices[i] < min_price:
min_price = prices[i]
if prices[i] > max_price:
max_price = max(max_price, prices[i] - min_price)
return max_price

<小时 />

参考资料

• 有关其他详细信息，您可以查看讨论区。其中有很多公认的解决方案、解释、多种语言的高效算法以及时间/空间复杂性分析。

Answer 3

这个问题不需要动态编程。您想找到x[i]- (最小价格高达 i(的最大值。因此，要找到销售时间，您只需评估(如果您正在处理numpy数组(sell = np.argmax(x- np.minumum.accumulate(x))对于购买时间，您需要'np.argmin(x[：sell](

如果您正在使用香草python(没有numpy(，只需实现累积minimum和argmin/argmax(非常简单(。

Answer 4

我不擅长python，但我可以告诉你我将如何做java。

public int maxProfit(int[] prices) {
int n = prices.length;
if(n==0) return 0;
int[] L = new int[n];
int[] R = new int[n];
L[0]=prices[0];
for(int i=1;i<n;i++){
L[i]=Math.min(L[i-1], prices[i]);
}
R[n-1]=prices[n-1];
for(int i=n-2;i>=0;i--){
R[i]=Math.max(R[i+1], prices[i]);
}
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
max = Math.max(max, R[i]-L[i]);
}
return max;
}

这种方法基本上是基于捕获雨水问题。