0x01 最大连续子段和
1. 题目描述
2 贪心 + 递推
思路：
如果我们选取了 k 个数，并且他们的和小于 0 ，那么这 k 个数肯定全都不包含在最大连续子段中。因为它们肯定会使得和更小。
因此，我们可以使用递推的形式，贪心的选择每一个数，如果加上当前数之后和小于 0，那么当前数肯定小于 0，并且，这一段连续子序列我们都不选。
不过，由于题目要求我们必须选择非空的子序列，那么我们就要考虑数组全都死负数的特殊情况了，此时，不存在非空连续区间和不为负数的情况，那么我们最后一个数都不选，得到的结果为 0。这显然是不行的（相当于我们一个数也没选），因为，我们要特判一下。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
int main()
{
int n, cur = 0;
int res = INT_MIN, seq_minx = INT_MIN;
cin >> n;
while (n -- )
{
int x; cin >> x;
if(cur + x < 0) cur = x;
else cur = cur + x;
res = max(res, cur);
}
// 特判
res = max(res, seq_minx);
cout << res << endl;
return 0;
}
3. dp
思路：
dp 只不过是递推的一种表现形式罢了，思路和递推差不过，但我们依然严格按照 [闫式 dp 法来分析]
状态方程：
f[i]表示以 i 结尾子段和的最大值。状态转移：根据是否包含第 i-1 个元素来划分子区间。
- 包含第 i-1 个元素，
f[i] = max(f[i],f[i-1]+w[i])- 不包含第 i-1 个元素，
f[i] = w[i]另外，对
f[]的初始化也要注意，求最大值要初始化为最小值，因为最大值可能为负数，所以不能用 0 作为最小值。f[0]=0，f[0]的含义是什么都不选，什么都不选当然为 0 了。
代码：
// 注：代码中有很多可以简化的地方
// 但是为了可读性更好，没有简化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
const int N = 2e5 + 10;
int n, w[N];
int f[N];
int res = INT_MIN;
int main()
{
memset(f, -0x3f, sizeof f);
f[0] = 0; // !
cin >> n;
for(int i = 1; i <= n; i ++ )
{
cin >> w[i];
// 包含第 i-1 个元素
f[i] = max(f[i], f[i - 1] + w[i]);
// 不包含第 i-1 个元素
f[i] = max(f[i], w[i]);
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
0x02. 最大连续子段和2
1. 题目描述
本题和上一题的差别在于，本题的子段要求最大和不能小于 0，如果数组元素全为负数，规定最大子段和为 0，这意味着最大值至少为 0，其次仍然要求连续
2. 贪心 + 递推
思路：
思路和上一题一模一样，差别在于，本题还需要找到最大连续子段的第一个元素和最后一个元素。如果数组元素全为负数，规定输出数组的第一个元素和最后一个元素。
下面我们讨论不是全负数的情况。
如果加上当前元素和仍然大于 0，当前元素就是尾了。
如果等于 0，因为题目要求输出头更小的，因此此时该元素仍然作为尾。
头稍微不好处理，因为题目要求要求最大连续子段和不能小于 0，所以当前元素小于 0 时，我们不能选它。
代码：
事实证明，把特判数组全负的情况单独拿出来，有利于我们 coding。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, w[N];
bool all_minus = true;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
{
cin >> w[i];
if(w[i] >= 0) all_minus = false;
}
// 特判全为负数的情况
if(all_minus)
{
cout << 0 << ' ' << w[1] << ' ' << w[n] << endl;
return 0;
}
// head=-1 表示我们的头还没有选
// 因为最大连续子段和可能为0，因此res要设置为<0的数
int res = -1, head = -1, tail = -1;
int cur = 0; // 最大连续子段的和
int l = -1, r = -1;
for(int i = 1; i <= n; i ++ )
{
if(cur + w[i] < 0)
{
// 此时 w[i]<0，我们肯定不选他
cur = 0;
// 标记，我们没有找到头
head = -1;
// 跳过，因为 cur=0 可能更新res=-1
continue;
}
else
{
cur += w[i];
if(head == -1) head = w[i];
tail = w[i];
}
if(cur > res)
{
res = cur;
l = head;
r = tail;
}
}
cout << res << ' ' << l << ' ' << r << endl;
return 0;
}
3. dp
0x02. 拓展
1. 题目描述
2. 前缀和 + 滑动窗口
非空和连续我们已经能解决了，问题是，长度受限怎么办？
通过一个滑动窗口来维护。
具体的我就不写了，看打开代码的注释或者参考吧。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
const int N = 3e5 + 10;
int n, m, w[N];
int s[N];
int res;
int main()
{
cin >> n >> m;
int seq_maxn = INT_MIN;
for(int i = 1; i <= n; i ++ )
{
cin >> w[i];
seq_maxn = max(seq_maxn, w[i]);
s[i] = s[i - 1] + w[i];
}
// 特判全为负数的情况
if(seq_maxn < 0)
{
cout << seq_maxn << endl;
return 0;
}
// 滑动窗口依然存储下标
// 滑动窗口的值是递增的
deque<int> q;
q.push_back(0); // 前缀和，不多做解释了！
for(int i = 1; i <= n; i ++ )
{
// w[i-m+1,i]
// s[i-m]
// 注意，我们存储的是前缀和下标，因此q.front()<i-m，而不是i-m-1
while(q.size() && q.front() < i - m) q.pop_front();
while(q.size() && s[i] <= s[q.back()]) q.pop_back();
q.push_back(i);
res = max(s[i] - s[q.front()], res);
}
cout << res << endl;
return 0;
}