题目大意
序列长 N（≤1000），求最长上升子序列（LIS）的最大元素和。非严格上升？题目为严格上升（value[j] < value[i]）。
DP 状态
dp[i]：以 a[i] 结尾的上升子序列最大和。
转移：dp[i] = a[i] + max{ dp[j] | j（若无则 0）
答案：max_i dp[i]
C++ 实现
#include
#include
#include
using namespace std;
const int MAXN = 1005;
int a[MAXN], dp[MAXN];
int main() {
int n;
while (scanf("%d", &n) == 1 && n) {
for (int i=1;i<=n;++i) scanf("%d", &a[i]);
int ans = 0;
for (int i=1;i<=n;++i) {
dp[i] = a[i];
for (int j=1;j
复杂度
- 时间：O(N²) = 10⁶，极快
- 空间：O(N)
优化：O(N log N) 求 LIS 长度（不适用最大和）
最大和问题无法直接用贪心+二分优化，因需比较和而非长度。若值域小可用树状数组/线段树优化至 O(N log V)。
样例验证
3 1 3 2 → LIS: 1,3 和=4
4 1 2 3 4 → 全序列和=10
4 3 3 2 1 → 单元素最大=3
