个人原创,转载请注明出处,谢谢!
一、目的
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
评论