最大子列和问题
分为两种类型:①不限制子序列的长度、②限制子序列的长度
问题一:不限制子序列的长度
题:Max Sum
解法一:贪心法,从前向后遍历序列,统计当前和,若当前和大于已有ans,则更新已有答案;若当前和小于0,则由贪心的思想,令当前和为零从新开始统计
下见代码:
//>>>Qiansui
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}
using namespace std;
const int maxm=1e6+5,inf=0x3f3f3f3f,mod=998244353;
ll n;
void solve(){
int c;
cin>>c;
ll t,sum,ans=0,pa,pb,f;
for(int i=1;i<=c;++i){
cin>>n;
f=pa=pb=1;
ans=-1000-5;
sum=0;
for(int j=1;j<=n;++j){
cin>>t;
sum+=t;
if(sum>ans){
ans=sum;
pb=j;
pa=f;
}
if(sum<0){
sum=0;
f=j+1;
}
}
cout<<"Case "<<i<<":\n";
cout<<ans<<' '<<pa<<' '<<pb<<'\n';
if(i<c) cout<<'\n';
}
return ;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
return 0;
}