最大子序列的和
问题描述:
求取数组中最大连续子序列和,例如给定数组为A={1, 3, -2, 4, -5}, 则最大连续子序列和为6,即1+3+(-2)+ 4 = 6。
思路:
因为最大 连续子序列和只可能是以位置0~n-1中某个位置结尾。当遍历到第i个元素时,判断在它前面的连续子序列和是否大于0,如果大于0,则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加;否则,则以位置i结尾的最大连续子序列和为元素i。
代码:
#include<cstdio>
int a[1000000];
int maxsequence(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]elsemaxhere += a[i]; //如果前面位置最大连续子序列和大于0,则以当前位置i结尾的最大连续子序列和为它们两者之和if (maxhere > maxsum) {maxsum = maxhere; //更新最大连续子序列和}}return maxsum;
}
int main()
{int t;while(~scanf("%d",&t)){for(int i=0;i<t;i++){scanf("%d",&a[i]);}int s=maxsequence(a,t);printf("%d\n",s);}return 0;
}