个人原创，转载请注明出处，谢谢！ 一、目的input: n个元素的数组； output: 在数组中查找相邻数的最大和； constrain: 如最大和为负数，则最大和为0，即一个也不选。 二、算法原理算法从数组的最左端x[0]开始，一直扫描到最右端x[n-1]，记下所碰到过的最大和，初始最大和为0。实际通过一个一个的增加元素来判断哪个子数组的和最大，抛弃小的和，留下大的和，最终得到最大和。就像我们看一排队伍中哪个人最高，我们从队伍的开头走起，发现一个比前面个子高的，就记下他来，然后往后走，又发现一个个子更高的，那就记下这个，忘掉之前的，再继续向后走，最终走到头，即可知道这个队伍中谁个子最高。和本算法唯一区别是，本算法不是求某个数最大，而是求哪几个连续数的和最大。如下图：   三、代码#include <stdio.h> #include <stdlib.h> #include <time.h>   #define MAXN 10000000 int n; float x[MAXN];     void sprinkle() {   int i;     for (i = 0; i < n; i++) {         x[i] = 1 - 2*( (float) rand()/RAND_MAX); } }   float get_max_sum () {   int i;     float maxsofar = 0, maxendinghere = 0;     for (i = 0; i < n; i++) {         maxendinghere += x[i];         if (maxendinghere < 0)             maxendinghere = 0;         if (maxsofar < maxendinghere)             maxsofar = maxendinghere;     }     return maxsofar; }   int main() {     float max_sum;       while (scanf("%d", &n) != EOF) {         sprinkle();         start = clock();         max_sum = -1.0; max_sum = get_max_sum(); printf(“max sum = %f\n”, max_sum); }       return 0; }   四、代码注解  /*使用随机数[-1，1]填充数组，使得数组内元素有正有负，且随机排布*/ void sprinkle() {   int i;     for (i = 0; i < n; i++) {         x[i] = 1 - 2*( (float) rand()/RAND_MAX); } }   /*获取最大连续和*/ float get_max_sum () {   int i; float maxsofar = 0, maxendinghere = 0;   for (i = 0; i < n; i++) {     /*不断累加连续和*/         maxendinghere += x[i];   /*如果发现累加和小于0，直接赋为0即可，因为最小和至少为0，即一个也不加的情况*/         if (maxendinghere < 0) {             maxendinghere = 0; }   /*如果标记的最大和小于当前的累加和，则进行替换，喜新厌旧J,抛弃以前的小值*/         if (maxsofar < maxendinghere) {             maxsofar = maxendinghere; }      }     return maxsofar; }   int main() {     float max_sum;   while (scanf("%d", &n) != EOF) {      /*初始化数组*/           sprinkle();          max_sum = get_max_sum();   printf (“max sum = %f\n”, max_sum);    }     return 0; }   本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/lijian818181/archive/2009/10/19/4697642.aspx

评论