主题:[原创]最大子段和问题
xuexiziji
[专家分:90] 发布于 2006-03-31 19:20:00
对n(n<20)的整数构成的系列(其中可以有正数和负数)由其中的任意多个连续项构成的子系列称为其子段。编程求最大的子段和。 好急啊!
回复列表 (共4个回复)
沙发
rickone [专家分:15390] 发布于 2006-03-31 22:12:00
题目不是很明确啊,希望说清楚一些,最好有例子。谢谢~
板凳
xuexiziji [专家分:90] 发布于 2006-04-01 13:27:00
不好意思啊,老师给的题目就这样的。
3 楼
Tokyson [专家分:90] 发布于 2006-04-04 11:39:00
我的想法很简单,求出长度为1的最大字段和,求出长度为2的最大字段和,。。。求出长度为n的最大字段和,然后取其最大值啊,这样的算法时间复杂度可能是O(n^2),自己实现一下吧
4 楼
duanjigang [专家分:40] 发布于 2006-04-04 14:53:00
/*
Author duanjigang@2006-4-4
*/
#include <stdio.h>
/*
第一个参数是数组名,第二个参数是数组中元素的个数(不是最大索引)
返回最大和子序列的和,并在运行过程中打印出了起始位置和子串长度
*/
int max_sum(int a[], int size);
int main(void)
{
int a[] = {1, -3, 6,5,-10, 6, -3 ,7,9,-3,-4, 5};
printf("%d\n", max_sum(a, 12));
}
int max_sum(int a[], int size)
{
int sum = -9999;
int i = 1;
int start = 1;
int length = 1;
int max_len = 0;
for(i = 0; i < size; i++)
{
int * p = a + i;
int len = size - i;
int j;
int tem;
for(j = 1; j <= len; j++)
{
int k;
tem = 0;
for(k = 0; k < j; k++)
tem += *(p + k);
//printf("%d %d => %d\n", i, j, tem);
if(tem > sum)
{
sum = tem;
start = i;
max_len = j;
}
}
}
printf("start index is %d <a[%d]>\nlength is %d\n", start, start, max_len);
return sum;
}
我来回复