10月27日备战Noip2018模拟赛11（B组）
T1 Maxsum最大子段和
题目描述
给出一个首尾相连的循环序列，从中找出连续的一段，使得该段中的数和最大。
输入格式
第一行一个整数n ，表示有n 个数。
第二行有ñ 个整数。
输出格式
只一个整数，表示最大的连续子段和。
输入样例
4
2 -4 1 4
输出样例
7
数据范围
对于100％的数据，1≤n≤100000，每个数的绝对值不超过100000。
思路
DP + 单调队列
算法一
因为这个字段是连续的（注意读题！注意读题！注意读题！重要的事情说三遍第一遍看题，哇，好简单，结果打完发现连样例都锅了）
所以最大子段和可能有两种情况（如下图）
那么对于第一种情况，我们就直接求最大值就可以了
第二种情况，可以求出中间白色部分的最小值，而且最小值的求法也可以转换为最大值，也就是求数列中相反数的最大值
最后再比较两种情况，求出最大子段和
（不要急， 代码后还有更简单的算法二， 休息一下，马上回来）
代码
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
const int MAXN = 1e6 + 5;
const int INF = -MAXN;
int n;
int a[MAXN], b[MAXN];
inline int read ();
int main ()
{
//freopen ("maxsum.in", "r", stdin);
//freopen ("maxsum.out", "w", stdout);
n = read ();
int maxx = INF;
int minn = MAXN;
long long tot = 0;
for (int i = 1; i <= n; ++ i){
a[i] = read ();
b[i] = -1 * a[i];
//a[2 * n + i] = a[i];
maxx = max (maxx, a[i]);
minn = min (minn, a[i]);
tot += a[i];
}
if (maxx < 0) { //特判一下全部是负数的情况
printf ("%d", maxx);
fclose (stdin);
fclose (stdout);
return 0;
}
long long ans = INF; // 求最大值
long long sum = 0;
for (int i = 1; i <= n; ++ i){
if (sum + a[i] < 0) sum = 0;
else sum += a[i];
ans = max (ans, sum);
}
if (minn >= 0){
printf ("%lld", ans);
fclose (stdin);
fclose (stdout);
return 0;
}
long long summ = INF; //求最小值
sum = 0;
for (int i = 1; i <= n; ++ i){
if (sum + b[i] < 0) sum = 0;
else sum += b[i];
summ = max (sum, summ);
}
ans = max (ans, tot + summ);
printf ("%lld", ans);
//fclose (stdin);
//fclose (stdout);
return 0;
}
inline int read ()
{
char ch = getchar ();
int f = 1;
while (!isdigit (ch)){
if (ch == '-') f = -1;
ch = getchar ();
}
int x = 0;
while (isdigit (ch)){
x = x * 10 + ch - '0';
ch = getchar ();
}
return x * f;
}
算法二
因为这个序列是一个环， 所以可以将它复制一遍接到后面， 这样序列的长度就变成了2n，而且显然，选取的子段长度不能超过n， 预处理出子段和使用DP求解
状态设计：dp[i] 表示以第i个数结尾的最大子段和
状态转移:
复杂度：
这样子的复杂度太大了， 使用单调队列优化DP，这样的复杂度是 注意这里要开longlong， 不然会wa2个点
使用单调队列考虑这样几个操作
若队首元素为x, 若， 则x出队， 直到若队尾元素x， 有, 则x出队在队尾插入i
代码（单调队列优化DP）
#include <iostream>
#include <cstdio>
#include <cctype>
#include <deque>
using namespace std;
const int MAXN = 2e5 + 5;
const long long INF = 9e18;
int n;
long long ans;
int a[MAXN];
long long preSum[MAXN];
deque <int> Q;
inline int read ();
int main ()
{
freopen ("maxsum.in", "r", stdin);
freopen ("maxsum.out", "w", stdout);
n = read ();
for (int i = 1; i <= n; ++ i){
a[i] = read ();
a[n + i] = a[i];
}
Q.push_back(0);
ans = -INF;
for (int i = 1; i <= 2 * n; ++ i){
preSum[i] = preSum[i - 1] + a[i];
}
for (int i = 1; i <= 2 * n; ++ i){
while (Q.size() && Q.front() < i - n) Q.pop_front();
ans = max (ans, preSum[i] - preSum[Q.front()]);
while (Q.size() && preSum[i] <= preSum[Q.back()]) Q.pop_back();
Q.push_back(i);
}
printf ("%lld", ans);
fclose (stdin);
fclose (stdout);
return 0;
}
inline int read ()
{
char ch = getchar ();
int f = 1;
while (!isdigit (ch)){
if (ch == '-') f = -1;
ch = getchar ();
}
int x = 0;
while (isdigit (ch)){
x = x * 10 + ch - '0';
ch = getchar ();
}
return x * f;
}
