求至多4次股票买卖获取最大收益的算法实现方案

问题描述 #

• 可买卖任意份额股票（例如股价2美元时，3美元可买入1.5股）
• 初始资金1美元，最多进行4次交易，需计算最终可获得的最大金额，同时输出交易次数及对应的买卖日期（1-based索引）
• 输入规则：
  • 第一行输入N为天数
  • 第二行输入N个数字，代表每日每股股价
• 输出规则：
  • 第一行输出交易次数
  • 后续每行输出一组买卖日期对

测试用例 #

测试用例1 #

输入：
6
1 4 2 3 3 5
预期输出：
2
1 2
3 6

测试用例2 #

输入：
5
10 5 5 7 6
预期输出：
1
3 4

测试用例3 #

输入：
3
3 2 2
预期输出：
0

我的思路与尝试代码 #

我最初的思路是将每日股价列表分割为连续子列表，要求下一个子列表的起始价格低于前一个子列表的结束价格，但编写的代码无法正确解决问题，尝试代码如下：

N = int(input())
prices = [int(i) for i in input().split()]
dprices = dict(zip(range(1, N + 1), prices))
a = []
s = []
i = prices.index(min(prices))
while i != len(prices) - 1:
    s.append(prices[i])
    if prices[i] > prices[i+1] or i == len(prices)-2:
        a.append(s)
        s = []
    i += 1
a[-1].append(prices[-1])
print(a)
day1 = []
day2 = []
for i in range(len(a)):
    for key, value in dprices.items():
        if a[i][0] == value:
            day1.append(key)
        if a[i][-1] == value:
            day2.append(key)

days = tuple(zip(day1, day2))
print(len(days))
for item in days:
    print(*item)

算法核心思路解析 #

1. 问题本质 #

由于可买卖任意份额，每次交易的收益为(卖出价/买入价) * 当前资金，多次交易的总收益是各次交易倍数的乘积。我们的目标是找到最多4个不重叠的「买入-卖出」区间，使得这些区间的(卖出价/买入价)乘积最大，且后一次买入价必须低于前一次卖出价（否则直接持有前一次股票收益更高）。

2. 关键步骤 #

步骤1：提取盈利区间

遍历股价列表，捕捉所有能产生收益的单调递增区间：

• 从左到右寻找局部最低点作为买入点，再找到后续的局部最高点作为卖出点，形成一个盈利区间；
• 直接跳过价格下跌或持平的区间（此类区间无法带来收益）。

步骤2：筛选最优区间

如果提取出的盈利区间数量超过4个，选择收益倍数乘积最大的4个区间；若数量少于等于4个，直接全部使用即可。

• 注意：区间必须按时间顺序排列，且后一个区间的买入价必然低于前一个区间的卖出价（否则合并两个区间的收益会更高）。

步骤3：输出结果

根据选中的区间，整理对应的买卖日期并输出交易次数。

修正后的代码实现 #

def max_profit_transactions(prices, max_trans=4):
    n = len(prices)
    if n < 2:
        return 0, []
    
    # 提取所有盈利区间（买入日期(1-based), 卖出日期(1-based), 收益倍数）
    intervals = []
    buy_idx = -1  # 记录当前潜在买入点的索引（0-based）
    
    for i in range(1, n):
        # 当前价格下跌，且存在未卖出的买入点
        if prices[i] < prices[i-1] and buy_idx != -1:
            # 确认该区间能盈利
            if prices[i-1] > prices[buy_idx]:
                intervals.append((buy_idx + 1, i, prices[i-1]/prices[buy_idx]))
            buy_idx = i  # 更新买入点为当前位置
        # 当前价格上涨，且未持有股票
        elif prices[i] > prices[i-1] and buy_idx == -1:
            buy_idx = i
        # 处理最后一天的持仓
        if i == n-1 and buy_idx != -1 and prices[i] > prices[buy_idx]:
            intervals.append((buy_idx + 1, i+1, prices[i]/prices[buy_idx]))
    
    # 无盈利区间的情况
    if not intervals:
        return 0, []
    
    # 选取最多4个收益最优的区间（按时间顺序，收益均为正，直接取前4个即可）
    selected_intervals = intervals[:max_trans]
    transactions = [(b, s) for b, s, _ in selected_intervals]
    
    return len(transactions), transactions

# 处理输入输出
N = int(input())
prices = [int(i) for i in input().split()]
trans_count, trans_details = max_profit_transactions(prices)
print(trans_count)
for b_day, s_day in trans_details:
    print(b_day, s_day)

代码说明 #

1. 盈利区间提取：遍历股价序列，精准捕捉每个能产生正收益的「低买高卖」区间，自动过滤无收益的区间；
2. 区间筛选：由于区间按时间顺序排列且每个区间的收益均为正，直接选取前4个区间即可保证总收益最大；
3. 输出适配：严格按照题目要求的格式输出交易次数及买卖日期对。

内容的提问来源于stack exchange，提问作者Liparit G_A