题解 P1115 最大子段和

link

容易想到朴素做法：

for (int l = 1; i <= n; ++i) {
    for (int r = 1; j <= n; ++j) {
        int v = s[r] - s[l - 1];
        ans = max(ans, v);
    }
}

但是显然 \(\mathrm{\color{#052242}TLE}\)

再回头看代码：想要 v 最大，只需要 \(\large{S_{l - 1}}\) 最小即可。

于是我们可以 \(O(n)\) 的动态更新 \(S_0 \sim S_{i-1}\) 最小值 \(\min_{1 \le i \le N}{S_i}\)

int m[N];
for (int i = 1; i <= n; ++i) {
    m[i] = min(m[i - 1], s[i]);
}

然后随 \(M_i\) 的更新，更新答案 \(ans = \max(S_i-M_{i-1})\) 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int a[N], m[N], s[N];
int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    
    
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        m[i] = min(m[i - 1], s[i]);
    }
    int ans = -2e4;
    for(int i = 1; i <= n; ++i)
    {
        ans = max(ans, s[i] - m[i - 1]);
    }
    cout << ans;
	return 0;
}//ACed

但是显然这份代码可以优化。

优化

1.

我们发现求完前缀和后，\(A_i\) 就没用了。

于是可以优化掉 \(A_i \to t\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int m[N], s[N];
int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    
    
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int t; cin >> t;
        s[i] = s[i - 1] + t;
        m[i] = min(m[i - 1], s[i]);
    }
    int ans = -2e4;
    for(int i = 1; i <= n; ++i)
    {
        ans = max(ans, s[i] - m[i - 1]);
    }
    cout << ans;
	return 0;
}//ACed

2.

两个循环都是 \(\mathrm{for\space\space i=1\sim N}\)。可以合并减小常数

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int m[N], s[N], ans = -2e4;
int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    
    
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int t; cin >> t;
        s[i] = s[i - 1] + t;
        m[i] = min(m[i - 1], s[i]);
        ans = max(ans, s[i] - m[i - 1]);
    }
    cout << ans;
	return 0;
}//ACed

3.

发现只需要用到 \(M_{i - 1}\) 于是 \(M_{i - 1} \to mi\) 且每次求完答案后更新 \(mi\) 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int mi, s[N], ans = -2e4;
int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    
    
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int t; cin >> t;
        s[i] = s[i - 1] + t;
        ans = max(ans, s[i] - mi);
        mi = min(mi, s[i]);
    }
    cout << ans;
	return 0;
}

4.

同理，只需要用到 \(S_i\)，优化掉即可

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int mi, s, ans = -2e4;
int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int t; cin >> t;
        s += t;
        ans = max(ans, s - mi);
        mi = min(mi, s);
    }
    cout << ans;
	return 0;
}