无限制最长连续的子序列和
https://www.acwing.com/problem/content/description/1481/
dp[i]=max(dp[i-1]+a[i],a[i]);
最终结果也就是在dp数组线性扫描找出最大值
int pos=max_element(dp+1,dp+1+n)-dp;
cout<<dp[pos]<<" ";
dp[i]表示以序列中第i个数字结尾的最大子段和
转移方程思考：如果选第i-1个数，那么由dp[i-1]转移过来，如果不选第i-1个数，那么它只能自己一个人作为一个子段存在，因为必须以第i个数结尾。
在给的题目中，还要求给出具体是哪段子段和最大，也就是左端点和右端点。
在我的代码中，是先求出来最大值，然后再排序所有符合最大值的子段的，按照题目要求左端和右端尽可能的小。
但这样在空间和时间上都是不优的，应该在线性扫描的时候就去维护最大值，一旦可以更新，也就更新左右端点。
有长度限制最长连续的子序列和
类型：单调队列优化dp
随着见的题目越来越多，单调队列也用的越来越多，单调队列用于找某个连续窗口的找到某个性质最小/大值，将这个本身O(n)的过程优化成O（1）
https://www.acwing.com/solution/content/67527/
上面的链接是题解，借鉴一下，个人认为写的很清楚。
题目描述
给定一个长度为 \(n\) 的序列 \(a\)，找出其中 元素总和最大 且 长度 不超过 \(m\) 的 连续子区间
分析
看到求一段 连续区间 的和的问题，会想到用 前缀和 进行优化，然后就是 枚举 区间的问题
暴力枚举 子区间是一种方法，但没有优化空间；因此不妨 枚举 子区间的 右端点
闫氏DP分析法
状态表示-集合 \(f_i\)：以 \(i\) 为 右端点，长度 不超过 \(m\) 连续子区间
状态表示-属性 \(f_i\)：区间的总和最大 \(Max\)
状态计算 \(f_i\)：
\[f_i = \max\big\{{ s_i - s_j }\big\} \qquad (1 \le i - j \le m) \]观察这个转移方程，首先这里的 \(j\) 是有范围的：\(i - m \le j \le i - 1\)
其次，\(s_i\) 作为一个常量，可以提到外面去：\(f_i = s_i - \min\big\{{ s_j }\big\} \qquad(1 \le i - j \le m)\)
从前向后 维护一个长度不超过 \(m\) 的区间的 最小值，就想到我们最熟悉的 滑动窗口模型 了
那么该状态 转移方程 就可以用 单调队列 进行优化了。这就是典型的应用场景，我们需要决策在当前m个j选哪一个j使得s[j]最小，用了单调队列维护我们就能快速知道，当前状态应该从哪一个状态转移过来最优。
Code
时间复杂度： \(O(n)\) （每个元素至多入队出队一次，每次转移又是 \(O(1)\) 的）
为了避免这个 高亮BUG，单调队列 q[] 改名为 que[] 了
由于这里 f[i] 没有相互依赖的关系，最后答案是统计所有 f[i] 的最大值
故我们直接用一个变量 res 来计算
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, m;
LL s[N], que[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]), s[i] += s[i - 1];
//处理前缀和
LL res = -1e18;
int hh = 0, tt = 0; que[0] = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && i - que[hh] > m) hh ++ ;
res = max(res, s[i] - s[que[hh]]);
while (hh <= tt && s[que[tt]] >= s[i]) tt -- ;
que[ ++ tt] = i;
}
printf("%lld\n", res);
return 0;
}