[求助]，有重谢(页 1) - 数据结构与算法

风之梦 发表于 2007-8-31 14:55

[求助]，有重谢

请帮忙，题为：考虑包含正整数的数组a ,函数fact(i,j)定义为a[i]到a[j]之间的连续元素之和。其中i,j为数组下标,i<=j,开发一个递归程序，确定使fact(i,j)取得最大值的i和j

风之梦 发表于 2007-8-31 14:57

题错了，小笨蛋，是包含正整数，还有负整数呢，还有负的

yuwg_le 发表于 2007-8-31 15:38

果然很难

leeco 发表于 2007-8-31 16:04

关键字：最大子段和，最大连续子序列 一搜一堆

风之梦 发表于 2007-8-31 19:19

哪们能帮一帮小妹妹我呀????

花之梦 发表于 2007-9-1 12:41

用递归有点难想呀，不知道怎么办呀，看来你还是要请教高手才行呀

aipb2007 发表于 2007-9-2 13:44

用什么递归，直接线性算法就行！

nuciewth 发表于 2007-9-2 13:58

int sum=0,b=0; for(i=0;i<n;i++) { if(b>0) b+=a[i]; //当前和为正,则可以以i为右端点成为最大子段和. else b=a[i]; // 不用修改 if(b>sum) sum=b; //更新b出现的最大和. } 其实就是一个简单的DP问题.

l19870910 发表于 2007-9-3 16:44

回复：（风之梦）题错了，小笨蛋，是包含正整数，还有...

这也算难> 为什么不回去好好看看书?

风之梦 发表于 2007-9-3 17:09

谢谢大家了。[em17]

xjlsgcjdtc 发表于 2007-9-5 15:34

int maxsubsum(int a,int left,int right) { int sum=0; if(left==right)sum=a[align=left]>0 ? a[align=left]:0; else{ int center=(left+right)/2; int leftsum=maxsubsum(a,left,center); int rightsum=maxsubsum(a,center+1,right); int s1=0,left=0; for(int i=center;i>=left;i--){ left+=a[i]; if(lefts>s1)s1=lefts; } int s2=0,rights=0; for(int i=center+1;i<=right;i++){ rights+=a[i]; if(lefts>s2)s2=rights; } sum=s1+s2; if(sum<leftsum) sum=leftsum; if(sum<rightsum) sum=rightsum; } return sum; }

论坛元老 发表于 2008-4-2 14:36

路过，顶一下

页: [1]

[求助]，有重谢

回复：（风之梦）题错了，小笨蛋，是包含正 整数，还有...

回复：（风之梦）题错了，小笨蛋，是包含正整数，还有...