题目描述:
给定一个数组 prices
,其中 prices[i]
表示第 i
天股票的价格。你需要设计一个算法,找到买入和卖出股票的最佳时机,使得利润最大化。
要求:
0
。输入格式:
n
,表示数组 prices
的长度。1 ≤ n
≤ 105n
个整数,表示 prices
数组中的元素,prices[i]
表示第 i
天的股票价格。0 ≤ prices[i]
≤ 104输出格式:
0
。示例:
输入:
6
7 1 5 3 6 4
输出:
7
说明:
2
天买入股票,价格是 1
,然后在第 3
天卖出股票,价格是 5
,在第 4
天买入股票,价格是 3
,然后在第 5
天卖出股票,价格是 6
,最大利润为 (5 - 1) + (6 - 3) = 7
。给定一个数组 prices
,每个元素代表第 i
天股票的价格。我们需要设计一个算法,通过多次买入和卖出操作,使得总利润最大化。每次买入股票之前,必须先卖出之前的股票。如果没有利润,返回 0
。
因为我们可以多次进行买入和卖出操作,所以我们只需要在股票价格上涨时进行买入并卖出即可,这样才能确保我们获得最大的利润。
由于股票的购买没有限制,因此整个问题等价于寻找 x 个不相交的区间 (l_i, r_i]
使得如下的等式最大化:
其中,l_i
表示在第 l_i
天买入,r_i
表示在第 r_i
天卖出。
同时我们注意到,对于 (l_i, r_i]
这个区间贡献的价值 a[r_i] - a[l_i]
,其实等价于 (li,li+1],(li+1,li+2],…,(ri−1,ri] 这若干个区间长度为 1 的区间的价值和,即:
因此问题可以简化为找 x 个长度为 1 的区间 (l_i, l_i+1]
使得:
的价值最大化。
从贪心的角度考虑,我们每次选择贡献大于 0 的区间,即能使得答案最大化,因此最后答案为:
ans=i=1∑n−1max(0,a[i]−a[i−1])其中 n
为数组的长度。
考虑题目中的例子 [1,2,3,4,5]
,数组的长度 n=5
。由于对所有的 1 ≤ i < n
都有 a[i] > a[i-1]
,因此答案为:
但是实际的交易过程并不是进行 4 次买入和 4 次卖出,而是在第 1 天买入,第 5 天卖出。
prices
数组。def maxProfit(prices):
# 初始化最大利润为 0
max_profit = 0
# 遍历价格数组,从第二天开始与前一天进行比较
for i in range(1, len(prices)):
# 如果今天的价格比昨天高,则可以获得利润
if prices[i] > prices[i - 1]:
# 累加利润
max_profit += prices[i] - prices[i - 1]
return max_profit
# 输入部分
n = int(input()) # 获取数组长度
prices = list(map(int, input().split())) # 获取价格数组
# 输出最大利润
print(maxProfit(prices))