股票买卖

题目描述

阿福已知股票未来 N 天的价格，希望买卖两次使利润最大，利润 = 卖出价 - 买入价；同一天可买卖多次，但第二次买入必须不早于第一次卖出。输入第一行是 T（数据组数），接下来每组一个 N 和 N 个价格（|p_i| ≤ 1e6，N ≤ 1e5）。每组输出一行表示最大利润。样例：第 1 组 5 14 -2 4 9 3 17 答案 28；第 2 组 6 8 7 4 1 -2 答案 2；第 3 组 18 9 5 2 答案 0。

思路

枚举拆分点 i，把两笔交易解耦成"前 i 天一笔最优" + “i 之后一笔最优”。前缀最优从左往右扫，维护最低买入价 low 与最大单笔利润 gain；后缀最优从右往左扫，对称维护最高卖出价 high。答案为 max(gain + g(i))，每组 O(N)。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:55
# update_at: 2026-09-30 03:55

import sys


def suffix_best(prices: list[int]) -> list[int]:
    """suf[i]：只在第 i 天及以后做一次买入卖出能拿到的最大利润（同天买卖记 0）。"""
    n = len(prices)
    suf = [0] * n
    high = prices[-1]  # 第 i 天右侧见过的最高价，只能当卖出价
    best = 0           # 窗口 [i, n-1] 内一次买卖的最大利润，天然不小于 0
    for i in range(n - 2, -1, -1):
        best = max(best, high - prices[i])  # 第 i 天买入、右侧最高价卖出
        suf[i] = best
        high = max(high, prices[i])
    return suf


def max_two_trades(prices: list[int]) -> int:
    """两次买卖的最大总利润：第二次买入允许与第一次卖出在同一天。"""
    suf = suffix_best(prices)
    ans = 0
    low = prices[0]  # 前缀里见过的最低买入价
    gain = 0         # 前缀 [0, i] 内做一次买卖的最大利润，也天然不小于 0
    for i, p in enumerate(prices):
        low = min(low, p)
        gain = max(gain, p - low)
        # 第一次买卖整体落在 [0, i]，第二次落在 [i, n-1]：卖出日 <= i <= 买入日
        ans = max(ans, gain + suf[i])
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        days = next(data)  # 天数 N
        prices = [next(data) for _ in range(days)]
        out.append(str(max_two_trades(prices)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:33
 * update_at: 2026-10-05 08:33
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 100005;

int n;                                 // 当前这一组数据的天数 N
int p[MAXN];                           // p[i]：第 i 天（1-indexed）的价格
int suf[MAXN];                         // suf[i]：第 i..N 天内只做一次买卖的最大利润（同天买卖记 0）

// 在价格序列 p[1..n] 上求两笔交易（第一笔卖出日 ≤ 第二天买入日）能拿到的最大总利润。
ll max_two_trades() {
    memset(suf, 0, sizeof(suf));

    // 反向扫描：suf[i] = 仅在第 i..n 天做一次买卖的最大利润
    int high = p[n];                 // 第 i 天右侧见过的最高卖出价
    int best = 0;                    // 第 i..n 天窗口里一次买卖的最大利润，天然不小于 0
    for (int i = n - 1; i >= 1; --i) {
        best = (best > high - p[i]) ? best : (high - p[i]); // 第 i 天买入、右侧最高价卖出
        suf[i] = best;
        high = (high > p[i]) ? high : p[i];
    }

    // 正向扫描：枚举拆分点 i，把两笔交易拆成 [1..i] 与 [i..n] 两个独立子问题
    ll ans = 0;
    int low = p[1];                  // 前缀里见过的最低买入价
    int gain = 0;                    // 前缀 [1..i] 内做一次买卖的最大利润，也天然不小于 0
    for (int i = 1; i <= n; ++i) {
        low = (low < p[i]) ? low : p[i];
        gain = (gain > p[i] - low) ? gain : (p[i] - low);
        ll cur = (ll)gain + suf[i]; // 第一笔整体落在 [0..i]，第二笔落在 [i..n]
        if (cur > ans) ans = cur;
    }
    return ans;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
        printf("%lld\n", max_two_trades());
    }
    return 0;
}

目录

题目描述

思路

参考代码