描述
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
输入
第1行，两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。
第2行， N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。
输出
一个整数，最大的和。
样例输入
5 2
2 -3 2 -1 2
样例输出
5
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
void paixu(int c[100000][3],int j){
for(int i = 0;i < j;i++){
for(int k = i + 1;k <= j;k++){
if(c[i][0] > c[k][0]){
int x = c[i][0];
c[i][0] = c[k][0];
c[k][0] = x;
x = c[i][1];
c[i][1] = c[k][1];
c[k][1] = x;
x = c[i][2];
c[i][2] = c[k][2];
c[k][2] = x;
}
}
}
}
int main(){
int n,m;
cin >> n >> m;
int a[100000];
int b[100000];
int c[100000][3];
int j = 0;
int zheng = 0,fu = 0;
int zhenghe = 0;
for(int i = 0;i < n;i++){
b[i] = 0;
}
for(int i = 0;i < n;i++){
cin >> a[i];
if(a[i] * b[j] >= 0){
b[j] += a[i];
}
else{
j++;
b[j] += a[i];
}
}
for(int i = 0;i <= j;i++){
if(b[i] >= 0){
zheng++;
zhenghe += b[i];
}
}
for(int i = 0;i <= j;i++){
c[i][0] = abs(b[i]);
c[i][1] = i;
if(b[i] >= 0) c[i][2] = 1;
else c[i][2] = 0;
}
int h = j;
int qq = 0;
while(1){
paixu(c,h);
if(zheng <= m){
cout << zhenghe << endl;
return 0;
}
else{
if(c[qq][2] == 1){
zheng--;
zhenghe = zhenghe - c[qq][0];
}
else if(c[qq][2] == 0){
if(c[qq][1] == 0 || c[qq][1] == h){
qq += 1;
}
else{
zheng--;
zhenghe -= c[qq][0];
c[qq][0] = c[qq][0] + c[c[qq][1] - 1][0] + c[c[qq][1] + 1][0];
for(int i = c[qq][1] - 1;i <= h;i++){
c[i][0] = c[i + 1][0];
c[i][1] = c[i + 1][1];
c[i][2] = c[i + 1][2];
}
for(int i = c[qq][1] + 1;i <= h;i++){
c[i][0] = c[i + 1][0];
c[i][1] = c[i + 1][1];
c[i][2] = c[i + 1][2];
}
h--;
}
}
}
}
return 0;
}
描述看错，原回答已删除
加点注释吧，看不懂你的思路。
我个人的想法是把序列整理成[+,-,+,-,+,....]的形式，然后将所有负数的绝对值排序取最大的M-1个数，求和再加上原数列的总和，应该就是最大值了。
思路就是先把所有数连在一次，然后切至多M-1次，因为有负数存在所以每次只切掉负数就能让总和增大，所以切M-1个绝对值最大的负数序列。
你这个代码关键还是注释，然后简单写写思路。
可参考
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int lNeg[200], sum = 0, index = -1;
bool lastIsNeg = false;
int n, m, a;
cin >> n >> m;
for( int i = 0; i < n; i++ ){
cin >> a;
sum += a;
if( a < 0 ){
if(lastIsNeg){
lNeg[index] += a;
} else {
lNeg[++index] = a;
lastIsNeg = true;
}
} else {
lastIsNeg = false;
}
}
index++;
if(index > m-1)
sort(lNeg, lNeg+index);
for( int i = 0; i < m-1 && i < index; i++ )
sum -= lNeg[i];
cout << sum << endl;
return 0;
}
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#define pa pair<int,int>
#define ll long long
#define inf 10000007
#define N 100007
using namespace std;
inline int read()
{
,f=;char ch=getchar();
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
struct cmp
{
bool operator()(pa a,pa b)
{
return abs(a.first)>abs(b.first);
}
};
priority_queue<pa,vector<pa>,cmp>q;
int n,m,tot,ans,sum;
int a[N],nxt[N],pre[N];
bool mark[N];
void del(int x)
{
mark[x]=;
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
}
int main()
{
n=read(),m=read(),tot=;
;i<=n;i++)
{
int x=read();
)a[tot]+=x;
else a[++tot]=x;
}//这里相乘比较巧妙。
n=tot;
;i<=n;i++)
) sum++,ans+=a[i];
;i<=n;i++)
{
nxt[i]=i+;
pre[i]=i-;
q.push(make_pair(a[i],i));
}
while (sum>m)
{
sum--;
while (mark[q.top().second]) q.pop();
int x=q.top().second;q.pop();
&&nxt[x]!=n+) ans-=abs(a[x]);
) ans-=a[x];else{sum++;continue;}
a[x]=a[pre[x]]+a[nxt[x]]+a[x];
del(pre[x]);del(nxt[x]);
q.push(make_pair(a[x],x));
}
printf("%d",ans);
}