P1115 最大子段和

题意:

求最大连续区间和

底层逻辑：

如果前面的最大区间和小于0，即已经成为“累赘”，就重启新区间，不再延续旧区间。 最后再排序dp（即记忆）数组。

动态规划表达式：

dp[i]=max(dp[i-1],0)+a[i];

具体代码及详细解析：

#include<bits/stdc++.h>
using namespace std;
int n;//题目要求
int main(){
	cin>>n;
	int a[n+1];//为了与dp数组对应，这里将a数组（即序列）长度改为了n+1,在实操中可改为n
	int dp[n+1]={0};//设置dp数组，预留一个dp[0]=0，以免第一个数运行时超限
	for(int i=1;i<=n;i++){//循环遍历序列
		cin>>a[i];//输入
		dp[i]=max(dp[i-1],0)+a[i];//是否抛开“累赘”，再加上这一数（因为题目要求区间连续）
	}
	sort(dp+1,dp+n+1);//排序，因为我们一开始设置dp从1开始，所以写sort的时候要注意起始位置
	cout<<dp[n];//因为已经经过排序，所以dp数组的最后一项（即dp[n]）就是最大连续区间和
	return 0;//The End,记得点赞！！！
}

#include<bits/stdc++.h>
using namespace std;
int n,a[200010],ans[200010]={0},pmax=-100000;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i],ans[i]=max(ans[i-1],0)+a[i];
	for(int i=0;i<n;i++)pmax=max(pmax,ans[i]);
	cout<<pmax;
	return 0;
}

蓟县压栈

#include<bits/stdc++.h>
using namespace std;int a,b,n,m=-1004;int main(){cin>>n>>a;b=max(0,a);for(int i=1;i<n;i++){cin>>a;m=max(m,b=max(a,b+a));}cout<<m;return 0;}

#include<bits/stdc++.h>
using namespace std;
int a[10000000];
int f[10000000];
int main(){
	int n,maxn=-100000; 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(f[i-1]>0){
		    f[i]=f[i-1]+a[i];	
		}
	    else{
	    	f[i]=a[i];
		}
	}
	for(int i=1;i<=n;i++){
		//cout<<f[i]<<" ";
		maxn=max(maxn,f[i]);
	}
	cout<<maxn;
}//我是c23litianyue发的

from 课件

#include<bits/stdc++.h>
using namespace std;
int main(){
int n,ans=INT_MIN,sum=0,num;
cin>>n;
for(int i=1;i<=n;i++){
	cin>>num;
    sum=max(sum+num,num);
    ans=max(ans,sum);
	
}

cout<<ans;
}