526互联

acwing1051. 最大的和

发布时间 2023-03-27 00:41:40作者: Pamper/

最大连续字段和问题：一段连续字段和 最大子段和

前后缀分解：登山,合唱队形

我们可以通过前后缀分解来处理两段字段和
预处理g[i]，表示1~i中最大的字段和
h[i] 表示i~n中最大的字段和

dp
状态表示：f[i]表示1~i中以i结尾的所有连续子序列的集合的最大值
状态计算：

  • 只含i
  • 区间长度至少是2, f[i] = max(w[i], f[i - 1] + w[i]) = w[i] + max(0, f[i - 1])
    因为每个状态只依赖前一个状态，所以f[i]可以用一个字母s来表示
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n;
int w[N], g[N], h[N];
int f[N];

int main ()
{
    int T;
    cin >> T;
    
    while(T --)
    {
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> w[i];
        f[0] = g[0] = -INF;     //空的话无解，为负无穷，保证不会转移
        for(int i = 1; i <= n; i ++)
        {
            f[i] = max(f[i - 1], 0) + w[i];
            g[i] = max(g[i - 1], f[i]);     //g[i]存的是前缀的最大值
        }
        
        h[n + 1] = f[n + 1] = -INF;
        for(int i = n; i; i --)
        {
            f[i] = max(f[i + 1], 0) + w[i];
            h[i] = max(h[i + 1], f[i]);     //h[i]存的是后缀的最大值
        }
        
        int res = -INF;
        for(int i = 1; i <= n; i ++)
            res = max(res, g[i] + h[i + 1]);
            
        cout << res << endl;
    }
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n;
int w[N], g[N], h[N];
int s;

int main ()
{
    int T;
    cin >> T;
    
    while(T --)
    {
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> w[i];
        g[0] = -INF;     //空的话无解，为负无穷，保证不会转移
        for(int i = 1, s = -INF; i <= n; i ++)      //这里一开始s要表示为-INF，表示一个数都没有，无解，保证不会转移
        {
            s = max(s, 0) + w[i];
            g[i] = max(g[i - 1], s);     //g[i]存的是前缀的最大值
        }
        
        h[n + 1] = -INF;
        for(int i = n, s = -INF; i; i --)
        {
            s = max(s, 0) + w[i];
            h[i] = max(h[i + 1], s);     //h[i]存的是后缀的最大值
        }
        
        int res = -INF;
        for(int i = 1; i <= n; i ++)
            res = max(res, g[i] + h[i + 1]);
            
        cout << res << endl;
    }
    
    return 0;
}