1007 Maximum Subsequence Sum (25 分)【难度: 一般 / 知识点: 最大子序列和】

https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168
方法一: 前缀和+枚举 时间复杂度: O(n²)

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int s[N],n; int startx,endx,ans=-1e9; bool flag; int main(void) {cin>>n;for(int i=1;i<=n;i++){cin>>s[i];if(s[i]>=0) flag=true;s[i]+=s[i-1];}if(!flag){cout<<0<<" "<<s[1]<<" "<<s[n]-s[n-1];return 0;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int sum=s[j]-s[i-1];if(sum>ans){ans=sum;startx=s[i]-s[i-1];endx=s[j]-s[j-1];}}}cout<<ans<<" "<<startx<<" "<<endx;return 0; }

方法二: 前缀和+贪心 时间复杂度O(n)
s[l,r]=s[r]-s[l-1] 故对每一个以r结尾的区间，我们让减的数s[l-1]最小，那么此时以r结尾的所有区间就可以求一个最大值。
即在[0,r-1]中取一个最小的值。
对于每一个r结尾的区间的最大和中，求一个最大值，即可求整个数组的一个最大的区间和。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int s[N],n; bool flag; int ans=-1e9,startx,endx; int main(void) {cin>>n;for(int i=1;i<=n;i++) {cin>>s[i];if(s[i]>=0) flag=true;s[i]+=s[i-1];}if(!flag){cout<<0<<" "<<s[1]<<" "<<s[n]-s[n-1];return 0;}int temp=1e9;int index=0;for(int i=1;i<=n;i++){if(temp>s[i-1]) temp=s[i-1],index=i;//保存前0-i-1中一个最小的前缀和int sum=s[i]-temp;if(sum>ans) ans=sum,startx=index,endx=i;}cout<<ans<<" "<<s[startx]-s[startx-1]<<" "<<s[endx]-s[endx-1];return 0; }

方法三: 双指针+贪心 时间复杂度O(n)
感觉写的有点问题，有一个测试点，应该是最后故意卡的过了

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int ans=-1e9,sum,startx,endx; int s[N],n; int main(void) {cin>>n;int flag=true;for(int i=0;i<n;i++){cin>>s[i];if(s[i]>=0) flag=false;} if(flag){cout<<0<<" "<<s[0]<<" "<<s[n-1];return 0;}for(int i=0,j=0;i<n;i++){sum+=s[i];while(sum<0) sum=sum-s[j],j++; if(sum>ans) {ans=sum;startx=s[j];endx=s[i];}}if(ans>0) cout<<ans<<" "<<startx<<" "<<endx;else cout<<0<<" "<<0<<" "<<0;return 0; }

总结

以上是生活随笔为你收集整理的1007 Maximum Subsequence Sum (25 分)【难度: 一般 / 知识点: 最大子序列和】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。