PTA测试题- 最大子列问题(C语言)

发布于 / C语言 / Comments Off on PTA测试题- 最大子列问题(C语言)

原题目:


原本是不会的,不过CSDN上的大神的blog给了我启发。先上代码:

#include <stdio.h>  
int main()  
    {  
        int i,n,max = 0,Max = 0,t;  
        scanf("%d",&n);  
        for(i = 0;i<n;i++){  
            scanf("%d",&t);  
            max += t;  
            if(max>Max)  
                Max = max;  
            if(max<0)  
                max = 0;      
        }   
        printf("%d",Max);  
  return 0;
    }

由于初学这种类型的题,在如何接收以空格分割的输入上很发愁(轻喷)。后来发现,直接for循环scanf就可以了= =,根本不用计算空格。。

在接收输入的内容后,原本想存入数组,再对数组进行计算,后来发现这样肯定超时,而且超时很久。。

这段算法的原理就是在输入的过程中直接将每次输入的时候,将求和结果存入临时变量max中,如果max<0,将max归零,这样避免了加入第一个负数。如果max>Max,将max赋值给Max。这样保证了Max最大。

运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » PTA测试题- 最大子列问题(C语言)
评论已关闭