【每天一道PAT】1007MaximumSubsequenceSum

思路

两种方法，一种方法暴力求解
一种方法实时读入，当当前相加和小于0时，当前相加和更新为0。

方法1 求出全部最大序列和
第五个测试点啊，理解有问题？不知道哪儿错了，数据为全是负数和0。希望有明白的读者加以指正。

#include
int num[10005];
int main()
{
int N;//数据个数
int this_sum=0, max_sum=0;//当前相加和、最大和
int m,n,temp;//记录子序列的左右边界下标
int count=0;//计数
scanf("%d", &N);
for (int i = 0; i {
scanf("%d",&num[i]);
if(num[i]<=0) count++;
}
if(count==N)
{
printf("0 %d %d",num[0],num[N-1]);
return 0;
}
m = n =0;
for (int i = 0; i {
this_sum = 0;
for (int j = i; j {
this_sum+=num[j];
if(this_sum >max_sum)
{
max_sum =this_sum;
n = i;
m = j;
}
}
}
printf("%d %d %d",max_sum, num[n], num[m]);
}


方法2 实时处理

#include
int num[10005];
int main()
{
int N;
int this_sum=0, max_sum=0;
int m,n,temp;
int count=0;
scanf("%d", &N);
for (int i = 0; i {
scanf("%d",&num[i]);
if(num[i]<0) count++;
}
if(count==N)
{
printf("0 %d %d\n",num[0],num[N-1]);
return 0;
}
this_sum=max_sum=num[0];
m = n =0;
for (int i = 1; i {
if(this_sum <0 )
{
this_sum = 0;
temp = i;
}
this_sum += num[i];
if(this_sum >max_sum)
{
max_sum =this_sum;
n = temp;
m = i;
}
}
if(max_sum <0)
printf("0 %d %d", num[0], num[N-1]);
else
printf("%d %d %d",max_sum, num[n], num[m]);
}