最大子序和

子序和是指在序列A中找一个区间 $[l,r]$ 使得区间的序列和最大。

此问题有两个情况， 第一种是不限制子序列的长度：

贪心解法 不限制长度就是可以全不选， 为0。定义 $start,end,p$ 为答案区间以及当前答案的区间起点， $sum$ 为当前答案的区间和。

当 $sum<0$ 时， 说明当前区间 $[p,i]$ 包含进答案区间的话只会有负贡献， 故直接删去， 令 $p=i+1,sum=0$ 。

当 $sum>maxsum$ 时， 可以更新最终答案， 同时更新 $start=p,end=i$ 即可。

时间复杂度 $O(N)$

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
 
    int maxsum = -0x3f3f3f3f, start = 1, end = 1, p = 1, sum = 0;
    for(int i = 1; i <= n; i++)
    {
        sum += a[i];
        if(sum > maxsum)
        {
            maxsum = sum;
            start = p;
            end = i;
        }
        if(sum < 0)
        {
            p = i + 1;
            sum = 0;
        }
    }
    cout << maxsum << " " << start << " " << end;
    cout << endl;
}
 

DP解法

定义状态 $f(i)$ 代表前 $i$ 项中的最大子序和。注意此时区间仍是连续的。

状态转移： $f(i)=max\{f(i-1)+a_i,a_i\}$

而输出答案的话， 因为状态定义保证了其结果一定是 $f(i)\subset [?,i]$ 区间内， 因此我们只需要记录每个状态对应的 $p_i$ 就行。定义 $res$ 存储最大子序列和的状态下标 $i$。

注意，在转移时，当 $f(i)=f(i-1)+a_i$ 时也更新 $p_i$， 这样的话才满足是字典序最小的答案。

#define S second
#define F first
#define pb push_back
#define pf push_front
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define MID l + r >> 1
#define mem(x,n) memset(x, n, sizeof x)
#define setPrec(n) cout << fixed << setpricision(n)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
using i64 = long long;
// #define debug
const int N = 1e5 + 10;
int a[N], n;
int f[N], p[N];
 
void solve() {
    memset(f, 0,sizeof f);
    memset(p, 0, sizeof p);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int sum = -0x3f3f3f3f, pos = 1;
    p[0]= 1;
    for(int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        if(f[i] <= f[i-1] + a[i])
        {
            p[i] = p[i-1];
            f[i] = f[i-1] + a[i];
        }
        else p[i] = i;
        
        if(sum < f[i])
        {
            sum = f[i];
            pos = i;
        }
    }
    cout << sum << " " << p[pos] << " " << pos << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, kase = 1;
    cin >> T;
    while(T--)
    {
        cout << "Case " << kase++ << ":\n";
        solve();
        cout << endl;
    }
    return 0;
}