最大子段和

题目描述

给出一个长度为 \(n\) 的序列 \(a\)，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 \(n\)。

第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个数字 \(a_i\)。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 \([3, 5]\) 子段 \(\{3, -1, 2\}\)，其和为 \(4\)。

数据规模与约定

• 对于 \(40\%\) 的数据，保证 \(n \leq 2 \times 10^3\)。
• 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 2 \times 10^5\)，\(-10^4 \leq a_i \leq 10^4\)。

本题思路：

设计状态：dp[N]严格以i为结尾的连续区间最大值
设计转移：即当前连续区间有由上一个区间加上当前值，或者是另起炉灶

dp[i] = max(dp[i - 1] + a[i], a[i]);

注意

设计状态时，要保证我们是在一个连续区间内进行操作(避免拼不上的情况)

AC_code(pull型)

#include <iostream>

using namespace std;

const int N = 2 * 1e5 + 10;

int dp[N];//1~i中最大连续和
int a[N];
int n;

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

void solve() {
    int res = -1e9;
    for(int i = 1; i <= n; ++ i) {
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        res = max(res, dp[i]);
    }
    cout << res << endl;
}

int main() {
    input();

    solve();
}

本人思路

沿用课上思路，设计了状态dp[N]表示为以1～i中的最大连续(其实已经错了，这样设计状态当区间，当扩展到1～i+1时，1～i最大连续区间最后一位可能不是i，而是其他值，这样即无法构成连续区间)
设计转移：

dp[i] = max(dp[i], dp[i] + a[i]);

用了01背包选or不选思路一眼假(成功写成01背包)，甚至正常求暴力都不会写的这么离谱，这样转移会导致只选择正数(也不满足连续区间定义)