HDU1231“最大连续子序列”

刺骨的言语ヽ痛彻心扉 2022-05-16 21:12 232阅读 0赞

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1231][http_acm.hdu.edu.cn_showproblem.php_pid_1231]

这个题就是模板

int maxsequence3(int a[], int len)
    {
        int maxsum, maxhere;
        maxsum = maxhere = a[0];   //初始化最大和为a【0】
        for (int i=1; i<len; i++) {
            if (maxhere <= 0)
                maxhere = a[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
            else
                maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
            if (maxhere > maxsum) {
                maxsum = maxhere;  //更新最大连续子序列和
            }
        }
        return maxsum;
    }

#include<stdio.h>
    int maxsum,begin,end;
    void maxsequence3(int a[], int len)
    {
        int  maxhere,flag;
        begin=end=maxsum =  a[0]; 
    	maxhere =0;  //初始化最大和为a【0】
        for (int i=0; i<len; i++) {
            if (maxhere < 0)
            {
            	flag=a[i];
            	  maxhere = a[i];
            }
                //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
            else	
            	maxhere += a[i];
                //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
            if (maxhere > maxsum) {
            	begin=flag;
    			end=a[i];
                maxsum = maxhere;  //更新最大连续子序列和
            }
        }
    
    }
    int main()
    {
    	int n,a[10001],i,j,t;
    	while(~scanf("%d",&n)&&n)
    	{
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    	maxsequence3(a,n);
    		if(maxsum<0)
    			printf("0 %d %d\n",a[0],a[n-1]);
    		else
    			printf("%d %d %d\n",maxsum,begin,end);
    	}
    	
    	return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1231]: http://acm.hdu.edu.cn/showproblem.php?pid=1231