PTA 实例1.1 最大子列和问题

实例1.1 最大子列和问题
题目要求：
给定K个整数组成的序列，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
代码：
解法1：

#include<stdio.h>int main(){int num,i=0,j=0,k=0;int a[100000];int max,sum=0;int flag=-1;  //有正数标志。 scanf("%d\n",&num);for(i=0;i<num;i++){scanf("%d",&a[i]);if(a[i]>=0){flag=1;}}if(flag==-1) {printf("0\n");return 0;}else{max=-1;for(i=0;i<num;i++){for(j=1;j<=num-i;j++){sum=0;for(k=i;k<i+j;k++){sum=sum+a[k];//printf("sum=%d  j=%d\n",sum,j);}if(max<sum){max=sum;}}}printf("%d\n",max);}return 0;
}

解法2：

max=-1;for(j=1;j<=num;j++){for(k=0;k<=num-j;k++){sum=0;for(i=k;i<k+j;i++){sum=sum+a[i];}if(max<sum){max=sum;}}}

此上两种解法在时间复杂度上不符要求，只提供相关思路。
解法3（正确解法）：

#include<stdio.h>int main(){int num,i=0,j=0,k=0;int a[100000];int max,sum=0;int flag=-1;  //有正数标志。 scanf("%d\n",&num);for(i=0;i<num;i++){scanf("%d",&a[i]);if(a[i]>=0){flag=1;}}if(flag==-1) {printf("0\n");return 0;}else{max=-1;for(i=0;i<num;i++){sum=0;for(j=i;j<=num;j++){sum=sum+a[j];if(max<sum){max=sum;}}}printf("%d\n",max);}return 0;
}

解题思路：
1、分别说一下1，2，3的思路。
一：分别顺序以各项为起首位置，子串长度从1开始到原串末尾即最大子串长度的加和。如数列“1，2，3，4，5，6”，比较：1,12,123,1234…2,23,234…的值。返回最大值。
二：从子串长度为1开始到原串长度，比较每个相应长度下子串和。如：“1，2，3，4，5，6”比较：“…12,23,34,45…234,345…”，返回最大值。
三：在解法一上进行更新，因为分析明确一中的思路后，发现k循环可有可无，只需要比较每一次新加入子串中的新和值与max之间的大小差异。省略了之前再次求和的那一步，时间复杂度为T(n^2)。