道聚城幸运召唤师活动:最大连续整数和

最大连续整数和

最大

连续整数和

动态规划

it

    【分析】面对这样的一道题目我们可以设计出很多种算法。先看看最一般的方法吧。把所有的连续段的和都算出来，再从中找一个最大的。我们设这些整数为a1、a2、……、an。把第i个到第j个的和记为S[i][j]。用这种方法也就是找到所有的S[i][j]（1<=i<=j<=n），而对于每一个S[i][j]需要遍历ai到aj之间的整数，所以容易判断时间复杂度为O(n^3)。这个参考程序如下

 【参考程序1】

 #include "stdio.h"

int main()

{

int a[1000];  //保存整数

int n;  //整数个数

int i , j , k;  //循环变量

int sum;  //和

int max;  //最大的和，即本题的结果

         //读入数据

         scanf("%d" , &n);

         for (i = 0; i < n; i ++) scanf("%d" , &a[i]);

         max = 0;

         //3重循环，时间复杂度为O(n^3)

         for (i = 0; i < n; i ++)

                   for (j = i; j < n; j ++)

                   {

                            sum = 0;

                            for (k = i; k <= j; k ++) sum += a[k];

                            if (sum > max) max = sum;

                   }

         printf("%d\n" , max);

         return 0;

}

    当然很容易想到一个改进的办法，因为S[i][j]=S[j]-S[i]。而S[i]我们可以用递推的方法求出，即S[i] = S[i-1] + a[i]，这样就可以通过扫描一遍求出所有的S[i]，然后再枚举所有的S[i][j]，因为这2个操作没有嵌套，所以时间复杂度为O(n^2)。

【参考程序2】

#include "stdio.h"

int main()

{

int a[1000];  //保存整数

int n;  //整数个数

int i , j;  //循环变量

int sum[1000];  //sum[i]表示从第0个元素到第i个元素的和

int max;  //最大的和，即本题的结果

         //读入数据

         scanf("%d" , &n);

         for (i = 0; i < n; i ++) scanf("%d" , &a[i]);

         max = 0;

         //预处理，算出所有的S1i

         sum[0] = a[0];

         for (i = 1; i < n; i ++) sum[i] = sum[i-1] + a[i];

         //2重循环，时间复杂度为O(n^2)

         for (i = 0; i < n; i ++)

                   for (j = i; j < n; j ++)

                            if (sum[j]-sum[i] > max) max = sum[j]-sum[i];

         printf("%d\n" , max);

         return 0;

}

    但是这还并不是这道题目的最简解答，下面看看这道题目最帅的算法吧。因为一个负数加上一个正数一定会使得正数变小。针对这一点，我们再把那一列整数分段来看，分成a1、……、ak，和a(k+1)（1<=k），这样如果2段要联系起来，第一段中选的整数必须到最右端，即要包括ak，所以我们可以找出最大的Sik(1<=i<=k)，记为Smax。如果Smax<0，则Smax取0。这样再看看与a(k+1)的和是不是正数，如果是正数则保留这个和作为下一次的Smax，因为前段最大的值加上这个数，构成的一定是这一段的Smax。当然如果与a(k+1)的和小于0，就Smax取0。每次对改变的Smax判断是否为最大值，这样就只要对数列遍历一遍即可求解。时间复杂度也就成了O(n)，而且这种算法的实现也非常的简单。

【参考程序3】

#include

int main()

{

int a[1000];  //保存整数

int n;  //整数个数

int i;  //循环变量

int sum;  //即为Smax

int max;  //最大的和，即本题的结果

         //读入数据

         scanf("%d" , &n);

         for (i = 0; i < n; i ++) scanf("%d" , &a[i]);

         max = 0; sum = 0;

    //一遍循环搞定，时间复杂度O(n)

         for (i = 0; i < n; i ++)

         {

                   sum += a[i];

                   if (sum < 0) sum = 0;

                   if (sum > max) max = sum;

         }

         printf("%d\n" , max);

         return 0;

}

特例:对于全为负数，求最大值即可