连续子段和问题（动态规划）

冷不防 2022-06-08 08:59 202阅读 0赞

【问题描述】

给出一段序列，选出其中连续且非空的一段使得这段和最大。

【输入格式】

输入文件的第一行是一个正整数 N，表示了序列的长度。第 2 行包含 N 个绝对值不大于 10000 的整数 A\[i\]，描述了这段序列。

【输出格式】输入文件仅包括 1 个正整数，为最大的子段和是多少。

【样例输入】

72 -4 3 -1 2 -4 3

【样例输出】

【数据规模与约定】

对于 40%的数据，有 N ≤ 2000。

对于 100%的数据，有 N ≤ 200000。

传统解法：求每次a\[i\]~a\[j\]的最大连续和（i<j<=n）;

#include<iostream>  
    #define MAXN 100001  
    using namespace std;  
    int main()  
    {  
        int a[MAXN];  
        int n,i,j,k;  
        int maxsum;//字段和最大值   
        int temp;//字段和   
        cin>>n;  
        for(i=1;i<=n;i++)  
        {  
            cin>>a[i];  
        }  
        maxsum=a[1];  
        for(i=1;i<=n;i++)//字段起点位置   
        {  
            for(j=i;j<=n;j++)//字段终点位置   
            {  
                temp=0;  
                for(k=i;k<=j;k++) temp=temp+a[k];//起点到终点求和   
                if(maxsum<temp) maxsum=temp;//字段最大值   
            }  
        }  
        cout<<maxsum<<endl;  
    }

//改进  
    #include<iostream>  
    #include<cstring>   
    #define MAXN 100001  
    using namespace std;  
    int main()  
    {  
        int s[MAXN],a[MAXN];  
        memset(s,0,sizeof(s));  
        int n,i,j;  
        int maxsum;  
        int temp;  
        cin>>n;  
        for(i=1;i<=n;i++)  
        {  
            cin>>a[i];  
            s[i]=a[i]+s[i-1];//预处理前缀和，eg s[2] = a[2]+s[1] = a[2]+a[1]  
        }  
          
        maxsum=a[1];  
        for(i=1;i<=n;i++)//起点  2  
        {  
            for(j=i;j<=n;j++)//终点  3  
            {  
                temp=s[j]-s[i-1];// temp=s[3]-s[1] =a[1]+a[2]+a[3]-a[1]=a[2]+a[3]  
                if(maxsum<temp) maxsum=temp;  
            }  
        }  
        cout<<maxsum;  
    }

#include<iostream>
    #define MAXN 200000
    using namespace std;
    int a[MAXN+10];
    int main()
    {
    	int i,j,s,n,maxn=0;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    	}
     
    	for(i=1;i<=n;i++)
    	{
    		s=a[i];
    		for(j=i+1;j<=n;j++)
    		{
    			s=s+a[j]; 
    			if(s>maxn) maxn=s;
    		}
    	}
    	cout<<maxn<<endl;
    }

动态规划解法：

满足最优子结构，满足无后效性。

求连续字段和时，只有整数加上一个数才可能越来越大，负数加上任一个数都会变小。

#include<iostream>
    #define MAXN 200000
    using namespace std;
    int a[MAXN+10];
    int getMaxArray(int a[],int n)
    {
    	int maxn=a[0],tmp=0,i;
    	for(i=1;i<=n;i++)
    	{
    		if(tmp>0) tmp+=a[i];
    		else tmp=a[i];//不能加“+”号 
    		maxn=max(maxn,tmp);
    	}
    	return maxn;
    }
    int main()
    {
    	freopen("seq.in","r",stdin);
    	freopen("seq.out","w",stdout);
    	int n,i,j;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    	}
    	cout<<getMaxArray(a,n)<<endl;
    	return 0;
    }