最大上升子序列和

题目描述

给定长度为 $n$ （ $1 \le n \le 1000$ ）的整数序列，元素取值范围 $0 \sim 10000$ 。按原下标顺序选出严格递增的子序列，求所选元素之和的最大值。注意最长上升子序列的和不一定最大，例如 $(100,1,2,3)$ 的最大上升子序列和为 $100$ 。

思路

设 $f[i]$ 为以第 $i$ 个数结尾的最大上升子序列和。枚举 $i$ 前面的位置 $j$ ，若 $a_j < a_i$ 则可接上， $f[i] = \max(f[j] + a_i)$ ；若前驱为空则 $f[i] = a_i$ 。最终答案为所有 $f[i]$ 的最大值。

参考代码

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#!/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:15
# update_at: 2026-10-04 10:24

import sys


def max_sum_rising(seq: list[int]) -> int:
    """f[i]：以 seq[i] 结尾的最大上升子序列和；答案取所有结尾位置里的最大值。"""
    f = [0] * len(seq)
    for i, value in enumerate(seq):
        # 接上"前面严格更小、和最大"的那一段；一个都接不上就自己单独成段
        f[i] = value + max((f[j] for j in range(i) if seq[j] < value), default=0)
    return max(f)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    length = next(data)  # 序列长度 N
    print(max_sum_rising([next(data) for _ in range(length)]))


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/**
 * 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:03
 * update_at: 2026-10-05 08:03
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // 序列最大长度

ll a[MAXN];   // 输入序列
ll f[MAXN];   // f[i] 表示以 a[i] 结尾的最大上升子序列和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i]; // 至少选 a[i] 一个元素
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) { // 严格递增才能接上
                f[i] = max(f[i], f[j] + a[i]);
            }
        }
        ans = max(ans, f[i]);
    }

    cout << ans << "\n";
    return 0;
}

最大上升子序列和

目录

题目描述

思路

参考代码