当前位置：首页 > news >正文

洛谷 P1115 最大子段和题解

news 2026/3/27 1:15:03

洛谷 P1115 最大子段和题解（线性 DP）

题意

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

数据范围与约定

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

题解

思路一：暴力（\(40\) \(\operatorname{pts}\)）

显然，暴力的时间复杂度可以达到 \(O(n^3)\)，加上前缀和优化，可以优化到 \(O(n^2)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
/*====================*/
using lnt = long long;
using pii = pair<int, int>;
using pll = pair<lnt, lnt>;
/*====================*/
#define endl "\n"
/*====================*/
const int INF = 0x3F3F3F3F;
const lnt INFLL = 0x3F3F3F3F3F3F3F3F;
/*====================*/
const lnt MOD = 998244353;
/*====================*/
void FileIn(const char* filename) {freopen(filename, "r", stdin);}
void FileOut(const char* filename) {freopen(filename, "w", stdout);}
/*====================*/
const int N = 2e5 + 10;
/*====================*/
int n, arr[N];
/*====================*/
lnt sum[N];
/*====================*/
void Init()
{cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}/*====================*/for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + arr[i];}
}
/*====================*/
void Solve()
{lnt ans = -INFLL;for (int l = 1; l <= n; l++){for (int r = l; r <= n; r++){ans = max(ans, sum[r] - sum[l - 1]);}}cout << ans << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGEFileIn("IN.txt");
#endifios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1; //cin >> T;while (T--) Init(), Solve();return 0;
}

思路二：DP（\(100 \operatorname{pts}\)）

按照右端点分类。考虑 \(f_i\) 表示以 \(a_i\) 为结尾的区间的最大子段和。把上述区间分为两类：第一类是长度等于 \(1\)；第二类是长度大于 \(1\)，显然长度等于 \(1\) 时，区间和是 \(a_i\)；长度大于 \(1\) 时，你可以选择前面的 \(f_{i - 1}\)，即前面的 \(a_{i - 1}, a_{i - 2}, \cdots a_1\) 的选择方案；也可以不选前面的，直接选 \(a_i\)，两种方案取最大值即可。则状态转移方程为：

\[f_i = \begin{cases}\max(f_{i - 1} + a_i, a_i) & i > 1 \\a_1 & i = 1 \end{cases} \]

#include<bits/stdc++.h>
using namespace std;
/*====================*/
using lnt = long long;
using pii = pair<int, int>;
using pll = pair<lnt, lnt>;
/*====================*/
#define endl "\n"
/*====================*/
const int INF = 0x3F3F3F3F;
const lnt INFLL = 0x3F3F3F3F3F3F3F3F;
/*====================*/
const lnt MOD = 998244353;
/*====================*/
void FileIn(const char* filename) {freopen(filename, "r", stdin);}
void FileOut(const char* filename) {freopen(filename, "w", stdout);}
/*====================*/
const int N = 2e5 + 10;
/*====================*/
int n, arr[N];
/*====================*/
lnt dp[N];
/*====================*/
void Init()
{cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}
}
/*====================*/
void Solve()
{dp[1] = arr[1];for (int i = 2; i <= n; i++){dp[i] = max(dp[i - 1] + arr[i], 1LL * arr[i]);}cout << *max_element(dp + 1, dp + n + 1) << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGEFileIn("IN.txt");
#endifios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1; //cin >> T;while (T--) Init(), Solve();return 0;
}

思路三：分治（\(100 \operatorname{pts}\)）

令：

\(f(l, r)\) 表示序列 \(a\) 中闭区间 \([l, r]\) 最大子段和；
\(\operatorname{Sum}(l, r)\) 表示序列 \(a\) 中闭区间 \([l, r]\) 的和，即 \(\sum \limits _{i = l} ^{r} a_i\)；
\(\operatorname{Pre}(l, r)\) 表示序列 \(a\) 中闭区间 \([l, r]\) 的最大前缀和；
\(\operatorname{Suf}(l, r)\) 表示序列 \(a\) 中闭区间 \([l, r]\) 的最大后缀和。

根据分治的思想，将序列 \(a\) 中的 \([l, r]\) 拆分为 \([l, \operatorname{mid}]\) 和 \([\operatorname{mid} + 1, r]\)。那么 \(f(l, r)\) 答案的来源可能为 \(f(l, \operatorname{mid})\)、\(f(\operatorname{mid} + 1, r)\)、\(\operatorname{Suf}(l, \operatorname{mid}) + \operatorname{Pre}(\operatorname{mid} + 1, r)\)。其实很容易理解：都在左半边、都在有半边、左半边和有半边都有，那就是左边的一段后缀和 \(+\) 右边的一段前缀和，取最大值即可。

下面给出 \(f(), \operatorname{Sum}(), \operatorname{Pre}(), \operatorname{Suf}()\) 的递推式和解释。

\[f(l, r) = \max(f(l, \operatorname{mid}), f(\operatorname{mid} + 1, r),\operatorname{Suf}(l, \operatorname{mid}) + \operatorname{Pre}(\operatorname{mid} + 1, r))；\\\operatorname{Sum}(l, r) = \operatorname{Sum}(l, \operatorname{mid}) + \operatorname{Sum}(\operatorname{mid} + 1, r)；\\\operatorname{Pre}(l, r) = \max(\operatorname{Pre}(l, \operatorname{mid}), \operatorname{Sum}(l, \operatorname{mid}) + \operatorname{Pre}(\operatorname{mid} + 1, r))；\\\operatorname{Suf}(l, r) = \max(\operatorname{Suf}(\operatorname{mid} + 1, r), \operatorname{Suf}(l, \operatorname{mid}) + \operatorname{Sum}(\operatorname{mid} + 1, r))。 \]

对于 \(f()\)，有这么几种可能：都在左半边、都在有半边、左半边和有半边都有，那就是左边的一段后缀和 \(+\) 右边的一段前缀和，取最大值即可；
对于 \(\operatorname{Sum}()\)，即为左半边的和 \(+\) 右半边的和；
对于 \(\operatorname{Pre}()\)，有这么几种可能：左半边的前缀和、左半边的全部 \(+\) 右半边的前缀和，取最大值；
对于 \(\operatorname{Suf}()\)，有这么几种可能：右半边的后缀和、右半边的全部 \(+\) 左半边的后缀和。

既然得出来了这些信息，代码就可以很轻松地写出来啦。

CODE

#include<bits/stdc++.h>
using namespace std;
/*====================*/
using lnt = long long;
using pii = pair<int, int>;
using pll = pair<lnt, lnt>;
/*====================*/
#define endl "\n"
/*====================*/
const int INF = 0x3F3F3F3F;
const lnt INFLL = 0x3F3F3F3F3F3F3F3F;
/*====================*/
const lnt MOD = 998244353;
/*====================*/
void FileIn(const char* filename) {freopen(filename, "r", stdin);}
void FileOut(const char* filename) {freopen(filename, "w", stdout);}
/*====================*/
struct Info
{int sum;int pre;int suf;int val;/*====================*/Info(int _sum = 0, int _pre = 0, int _suf = 0, int _val = 0){sum = _sum, pre = _pre, suf = _suf, val = _val;}/*====================*/friend Info operator+(const Info& l, const Info& r){Info res;res.sum = l.sum + r.sum;res.pre = max(l.pre, l.sum + r.pre);res.suf = max(r.suf, r.sum + l.suf);res.val = max( {l.val, r.val, l.suf + r.pre} );return res;}
};
/*====================*/
const int N = 2e5 + 10;
/*====================*/
int n, arr[N];
/*====================*/
Info Build(int l, int r)
{if (l == r){return Info(arr[l], arr[l], arr[l], arr[l]);}int mid = (l + r) >> 1;return Build(l, mid + 0) + Build(mid + 1, r); 
}
/*====================*/
void Init()
{cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}
}
/*====================*/
void Solve()
{cout << Build(1, n).val << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGEFileIn("IN.txt");
#endifios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1; //cin >> T;while (T--) Init(), Solve();return 0;
}