模板
教程
环境
性能
功能
管理
求一个数组中最大的相邻元素之和
求一个数组中最大的相邻元素之和 举例： 数组m如下：23-6343-252-3 则结果为m[3-8]之和15 yuxh 回复于：2004-12-28 20:27:41 这个题还是有一定难度的 [code:1:d75ca1f6ff]voidMaxSumint*m,intn inti,start=0,end=0,max,sum,start1=0,end1=0,sum1=0; sum=max=
求一个数组中最大的相邻元素之和
举例：
数组m如下：2 3 -6 3 4 3 -2 5 2 -3
则结果为m[3-8]之和15
| yuxh 回复于：2004-12-28 20:27:41 |
| 这个题还是有一定难度的
[code:1:d75ca1f6ff]void MaxSum(int *m, int n) { int i, start=0, end=0, max, sum, start1=0, end1=0, sum1=0; sum = max= m[0]; if(m[0] > 0) sum1 = m[0]; for(i=1; i<n; i++) { if(m[i] > 0 && sum1 == 0) start1 = i; sum1 += m[i]; if(sum1 > 0) end1 = i; else sum1 = 0; if(sum1 > 0 && sum1 > max) { start = start1; end = end1; max = sum1; } sum += m[i]; if(sum > max) { if(end < i-1 ) { start = end+2; max = sum - max - m[end+1]; sum = max; } else max = sum; end = i; } } printf("start %d, end %d, sum %d\n", start, end, max); } main() { int m[10] = {2,3,-6,3,4,3,-2,5,2,-3}; MaxSum(m, 10); } [/code:1:d75ca1f6ff] 自己感觉差不多 |
| aero 回复于：2004-12-28 22:40:52 |
| 题是啥意思啊？没明白。 |
| yuxh 回复于：2004-12-29 08:42:05 |
| 就是把相邻的数加起来，取最大值
2 3 -6 3 4 3 -2 5 2 -3 中 3+4+3+(-2)+5+2=15是相邻数相加最大的 下标是从3到8号 |
| liulang0808 回复于：2004-12-29 10:51:36 |
| 用循环嵌套可以的!不过好象比较浪费资源的! |
| wangxg2 回复于：2004-12-29 11:10:04 |
| 不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。 |
| liulang0808 回复于：2004-12-29 11:12:04 |
| C的语法已经不太熟悉了,简单描述如下:
MAX=M[0]是最终的最大值; K为中间作为比较用的; FOR (I=0;I<=N;I++) 其中N是数组的的大小 {K=M[I]; FOR (J=I;J<=N-1;I++) {IF (MAX<K) THEN MAX=K; K=K+M[J+1]; } } 已经两年多没有搞编程方面的东西了. 可能存在错误,请指教! |
| yuxh 回复于：2004-12-29 11:13:09 |
| 考虑下面的这一种普遍情况：
.......m[start]....m[end].....m[start1].....m[end1] m[i] 其中从start到end是结点i之前(称之为“目前”)相邻和最大的序列，和为max 从start1到end1(end1=i-1)是目前相加和>0的最长序列，和为sum1，如果这样的序列不存在，则sum1=0 用sum表示从start到目前的和 现在新加入了一个结点m[i]，看看最大相邻和序列会发生什么样的变化： 1、sum1 += m[i]; 若sum1 > max，则从start1到i就变成了最大序列，修正start，end，max； sum1 < 0，则表示最近的相邻和>0的序列不存在了，sum1 = 0; 否则，修正end1, sum1 2、经过上一步调整后，sum+=m[i]; 如果sum > max，则从start到i就最成了最大序列，修正end，max 其它的情况保持不变 只需对序列扫描一遍，即可得到相邻和最大序列，O(n) |
| aero 回复于：2004-12-29 11:14:35 |
| ^_^，全是负数，应该是0吧。因为什么也不加。 |
| yuxh 回复于：2004-12-29 11:26:24 |
| [quote:f74f43b509="wangxg2"]不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。[/quote:f74f43b509]
:em06: 是有这么个问题 所以sum1不应该是最近>0的最长序列，而应该是最近最大或和>0的最长序列 改一下： [code:1:f74f43b509]void MaxSum(int *m, int n) { int i, start=0, end=0, max, sum, start1=0, end1=0, sum1=0; sum = max= m[0]; sum1 = m[0]; for(i=1; i<n; i++) { if(m[i] > sum1 && sum1 <= 0) { start1 = end1 = i; sum1 = m[i]; } else { sum1 += m[i]; if(sum1 > 0) end1 = i;else sum1=m[i]; } if(sum1 > max) { start = start1; end = end1; max = sum1; } sum += m[i]; if(sum > max) { if(end < i-1 ) { start = end+2; max = sum - max - m[end+1]; sum = max; } else max = sum; end = i; } } printf("start %d, end %d, sum %d\n", start, end, max); } main() { int m[10] = {-2,-3,-6,-3,-4,-3,-2,-1,-2,-3}; MaxSum(m, 10); } [/code:1:f74f43b509] |
| guile 回复于：2004-12-29 11:51:54 |
| 我的想法是这样：
1如果全是负数，那么返回值就是最大的那个负数，存到sum 2当遇到正数时，就考虑求和sum1。一直求到最后一个正数， 3但是当后面第二个正数大于后面第一个非正数的绝对值，就把这两个数加到sum1，然后走到第2步。否则，4 4sum1和sum比较，看是否要更改。 代码实现如下 [code:1:52292c0cf9] #include<iostream> using namespace std; void MaxSum(int* ip,int size) { int sum=ip[0],sum1=sum,start=0,end=0,start1,end1; int i=0; while(ip[i]<0&&i<size) { if(ip[i]>sum) { sum=ip[i]; start=end=i; } } while(i<size) { if(ip[i]>0) { start1=end1=i; sum1=0; while((end1<size)&&(ip[end1]>0)) { sum1+=ip[end1]; end1++; i=end1+1; if((ip[end1]<=0)&&(end1<size-1)&&(ip[end1+1]>-ip[end1])) { sum1+=ip[end1]+ip[end1+1]; end1+=2; } } if(sum1>sum) { start=start1; end=end1-1; sum=sum1; } } else { i++; } } cout<<"Start: "<<start<<endl <<"End: "<<end<<endl; for(i=start;i<end;i++) cout<<ip[i]<<" "; cout<<endl <<"The sum is "<<sum<<endl; } int main() { int a[]={2,3,-6,3,4,3,-2,5,2,-3}; MaxSum(a,10); return 0; }[/code:1:52292c0cf9] |
| liulang0808 回复于：2004-12-29 11:52:46 |
| 强 |
| guile 回复于：2004-12-29 11:54:54 |
| 虽然上面的代码看上去循环有嵌套，不过还是O(n)的算法，内循环改变的也是外循环的i
另外i和end1两个变量其实可以合并，不过为了容易阅读一点，还是多用了一个变量 |
| guile 回复于：2004-12-29 12:13:09 |
| [quote:e95629880a="guile"][/quote:e95629880a]
不行，发现自己第三步考虑太简单了，等我改改 |
| assiss 回复于：2004-12-29 12:50:06 |
| [code:1:1c062cd504]
#include <stdio.h> #include <stdlib.h> void MaxSum(int *m, int n) { int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0; max=m[0]; for(i=0;i<n && m[i]<=0;i++)//我觉得把负数单独拿出来考虑更好一点 { if(m[i]>max) { max=m[i]; start=i; } } if(i==n) { printf("start %d, end %d, sum %d\n", start, start, max); return; } start2=start=istart=i; for(i=n-1;i >-1 && m[i]<=0;i--);//末尾的非正数也拿掉,少做几次加法 iend=i; max=m[start]; sum=0; for(i=istart;i<=iend;i++) { sum+=m[i]; sum2+=m[i]; if(sum>max) { end=i; max=sum; } if(sum2<=0 && m[i]>0)//这里用的算法和yuxh的一样.真佩服yuxh,算法这方面做得太好了 { sum2=m[i]; start2=i; } if(sum2>max) { start=start2; end=i; max=sum2; } } printf("start %d, end %d, sum %d\n", start, end, max); } int main() { int m[10] = {-2,-3,-6,-3,-4,-3,-2,-1,-2,-3}; MaxSum(m, 10); return 0; } [/code:1:1c062cd504] |
| guile 回复于：2004-12-29 12:52:35 |
| 算法如下
1用sum,start,end储存最大和，开始下标，结束下标。 如果数组里开始遇到的都是负数，那么sum保存的就是最大的负数 2当遇到正数的时候，开始用sum1求和，start1代表开始下标，end1要用来探测所以存储的是结束下标的下一个 求和一直求到遇到非正数或者结束 如果不是正数，探测下一个下标作为开始 3把后面的非正数和sum1加到sum2，再加下一个正数。 如果sum2>=sum1，则用sum2替换sum1，回到2 否则4 4比较sum和sum1，sum1大的话替换掉sum，以后的探测下标从end1-1开始 [code:1:8a5829c53d]#include<iostream> using namespace std; void MaxSum(int* ip,int size) { int sum=ip[0],sum1,sum2,start=0,end=0,start1,end1; int i=0; while(i<size&&ip[i]<0) { if(ip[i]>sum) { sum=ip[i]; start=end=i; } i++; } while(i<size) { if(ip[i]>0) { start1=end1=i; sum1=0; while((end1<size)&&(ip[end1]>=0)) { sum1+=ip[end1]; end1++; i=end1; if((i<size)&&(ip[i]<=0)) { sum2=sum1; while((i<size)&&(ip[i]<=0)) { sum2+=ip[i]; i++; } if(i<size) { sum2+=ip[i]; if(sum1<=sum2) { end1=i+1; sum1=sum2; } } } } if(sum1>sum) { start=start1; end=end1-1; sum=sum1; } } else { i++; } } cout<<"Start: "<<start<<endl <<"End: "<<end<<endl; for(i=start;i<=end;i++) cout<<ip[i]<<" "; cout<<endl <<"The sum is "<<sum<<endl; } int main() { int a[]={-2,-3,-6,3,4,-1,-2,5,2,-3}; MaxSum(a,10); return 0; }[/code:1:8a5829c53d] |
| yuxh 回复于：2004-12-29 13:01:49 |
| assiss的程序还有问题呀!
int m[10] = {2,3,-6,3,4,3,-2,5,2,-3}; start 0, end 8, sum 14 |
| yuxh 回复于：2004-12-29 13:15:30 |
| guile的算法也有问题
int a[]={2,3,-4,3,4,3,-2,5,2,-3}; start:3, end:8, sum:15 |
| assiss 回复于：2004-12-29 13:15:38 |
| [quote:7efec39a79="yuxh"],3,-6,3,4,3,-2,5,2,-3};
start 0, end 8, sum 14[/quote:7efec39a79] sorry,还没完全领会精神就乱发程序了. :oops: :oops: :oops: :oops: 再来,反正脸皮厚 [code:1:7efec39a79] #include <stdio.h> #include <stdlib.h> void MaxSum(int *m, int n) { int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0; max=m[0]; for(i=0;i<n && m[i]<=0;i++) { if(m[i]>max) { max=m[i]; start=i; } } if(i==n) { printf("start %d, end %d, sum %d\n", start, start, max); return; } end=start2=start=istart=i;//加了个END.因为发现如果只有一个正数时END有误. for(i=n-1;i >-1 && m[i]<=0;i--); iend=i; sum2=sum=max=m[start]; for(i=istart+1;i<=iend;i++) { sum+=m[i]; sum2+=m[i]; if(sum>max) { end=i; max=sum; } if(m[i-1]<=0 && m[i]>0) { sum2=m[i]; start2=i; } if(sum2>max) { start=start2; end=i; sum=max=sum2;//这里又修改了.唉.惭愧. } } printf("start %d, end %d, sum %d\n", start, end, max); } int main() { int m[10] = {2, 3, -6, 3, 4, 3, -2, 5, 2, -3}; MaxSum(m, 10); return 0; } [/code:1:7efec39a79] |
| guile 回复于：2004-12-29 13:25:43 |
| [quote:6cb4dcb262="yuxh"]4,3,4,3,-2,5,2,-3};
start:3, end:8, sum:15[/quote:6cb4dcb262] 恩，考虑中 |
| yuxh 回复于：2004-12-29 13:30:20 |
| assiss：
if(m[i-1]<=0 && m[i]>0) { sum2=m[i]; start2=i; } 这样子是不行的:-( int m[10] = {2, 3, -6, 3, 4, 3, -7, 5, 3, -3}; start 3, end 5, sum 10 |
| assiss 回复于：2004-12-29 13:35:53 |
| [quote:90f4e8b31b="yuxh"], 3, -6, 3, 4, 3, -7, 5, 3, -3};
start 3, end 5, sum 10[/quote:90f4e8b31b] 已经改了.嘿嘿.这次速度比你快一点.刚贴出来就看到错了......不过你F5的速度也太快了吧??? |
| yuxh 回复于：2004-12-29 13:37:30 |
| F5是啥东西？
我看你们两个的程序看得累死 :D :D :D |
| assiss 回复于：2004-12-29 13:43:11 |
| [quote:96778c1ee6="yuxh"]F5是啥东西？
我看你们两个的程序看得累死 :D :D :D[/quote:96778c1ee6] 习惯上把刷新说成"F5",呵呵,当年用IE落下的毛病. 我第一次贴出修改的程序,里面有你说的问题.但我在很短的时间内就修改了,竟然还是让你看到了,嘿嘿,所以说你的F5速度很快. 你的算法功底太强了,怎么学的?我现在设计算法,总会出错,然后一点一点修改,最后得到一个也不知道是不是正确的结果.不知道是不是因为太懒了,不肯从数学角度上考虑这个问题. |
| yuxh 回复于：2004-12-29 13:50:08 |
| 偶以前数学系的，大学里就学过BASIC
对于复杂一点的问题先在纸上列一下，把数学问题先搞清楚，不要急着写程序，不然出了问题也不知道什么问题，一点一点地改，把别人看出来的问题补掉，但也不明白最后还会不会出问题，这样不好。 |
| twen345 回复于：2004-12-29 14:02:44 |
| [quote:767c48a497="assiss"]
习惯上把刷新说成"F5",呵呵,当年用IE落下的毛病. 我第一次贴出修改的程序,里面有你说的问题.但我在很短的时间内就修改了,竟然还是让你看到了,嘿嘿,所以说你的F5速度很快. 你的算法功底太强了,怎么学的?我现在设计..........[/quote:767c48a497] nod,yuxh的算法就是厉害！ |
| assiss 回复于：2004-12-29 14:08:49 |
| [quote:f8814efa68="yuxh"]偶以前数学系的，大学里就学过BASIC
对于复杂一点的问题先在纸上列一下，把数学问题先搞清楚，不要急着写程序，不然出了问题也不知道什么问题，一点一点地改，把别人看出来的问题补掉，但也不明白最后还会不会出问�.........[/quote:f8814efa68]受益匪浅啊.数学系出来的就是不一样.做程序果然很有前途. |
| aero 回复于：2004-12-29 15:22:57 |
| [quote:75ab43f012="assiss"]芤娣饲嘲?.数学系出来的就是不一样.做程序果然很有前途.[/quote:75ab43f012]
嗯，的确，学数学的出来，就是有一种高屋建瓴的感觉。唉，数学俺是学不好了啊。 yuxh的算法的确不错。可是有一个地方没看明白。感觉那个sum1没什么用啊。下面是我用yuxh的算法写的程序。附加了一个笨笨的O(n2)算法做验证。 [code:1:75ab43f012] #include <stdio.h> #include <stdlib.h> int find_max(int ary[], int *p_start, int *p_end, int num); void test_find_max(int ary[], int num); int main(void) { int *ary, n, i; int max, start, end; printf("How many numbers: "); scanf("%d", &n); ary = (int *)malloc(n*sizeof(int)); if (!ary) { perror("ary malloc"); exit(1); } printf("Input numbers: "); for (i = 0; i < n; i++) scanf("%d", &ary[i]); max = find_max(ary, &start, &end, n); printf("max = %d, start = %d, end = %d\n", max, start, end); test_find_max(ary, n); exit(0); } int find_max(int ary[], int *p_start, int *p_end, int num) { int start, end, max, start1, end1, sum, i; start = end = start1 = end1 = 0; max = ary[0] > 0 ? ary[0] : 0; sum = max; for (i = 1; i < num; i++) { if (end1 == i-1) { sum += ary[i]; if (sum > 0) { end1++; if (sum > max) { start = start1; end = end1; max = sum; } } } else { if (ary[i] >= 0) { sum = ary[i]; start1 = end1 = i; } } } *p_start = start; *p_end = end; return max; } void test_find_max(int ary[], int num) { int max, sum, start, end; int i, j; max = sum = start = end = 0; for (i = 0; i < num; i++) { sum = 0; for (j = i; j < num; j++) { sum += ary[j]; if (sum > max) { max = sum; start = i; end = j; } } } printf("Test result:\n"); printf("max = %d, start = %d, end = %d\n", max, start, end); return ; } [/code:1:75ab43f012] |
| yuxh 回复于：2004-12-29 16:20:32 |
| aero言之有理，这样的话可以把end1也去掉
[code:1:f3a84e1167]void MaxSum(int *ary, int n) { int i, start=0, end=0, start1=0, max, sum; max=ary[0]; for(i=1;i<n && ary[i]<=0;i++) { if(ary[i]>max) { max=ary[i]; start=end=i; } } sum = max > 0 ? max : 0 ; for(; i<n; i++) { if(ary[i] > 0 && sum <= 0) start1 = i; sum += ary[i]; if (sum > max) { start = start1; end = i; max = sum; } else if(sum < 0) sum = 0; } printf("start %d, end %d, sum %d\n", start, end, max); } main() { int m[10] = {2,3,-6,3,4,3,-2,5,2,-3}; MaxSum(m, 10); } [/code:1:f3a84e1167] |
| yuxh 回复于：2004-12-29 16:29:18 |
| 有个错误，上面的程序已更正!
失败!又发现一个错误，上面的程序再次作了更正 |
| assiss 回复于：2004-12-29 17:03:31 |
| 老天啊,yuxh是不是还准备把程序简化到一两行?受不了了,很受伤,很受打击.aero,借个肩膀用一下.哇哇哇................ |
| guile 回复于：2004-12-29 22:28:26 |
| 佩服yuxh的算法，觉得我考虑问题真是含糊不清。
后来把程序又写了一下，先贴了再研究yuxh的程序 [code:1:c280388c1b]#include<iostream> using std::cout; using std::endl; void MaxSum(int* ip,int size) { int sum=ip[0],sum1=0,start=0,end=0,start1,end1; int i=0; while(i<size&&ip[i]<=0) { if(ip[i]>sum) { sum=ip[i]; start=end=i; } i++; } while(i<size) { if(ip[i]>0) { sum1=ip[i]; start1=end1=i; if(sum1>sum) { sum=sum1; start=start1; end=end1; } i++; while((i<size)&&(sum1>0)) { if(sum1+ip[i]>0) { end1=i; sum1+=ip[i]; if(sum1>sum) { sum=sum1; start=start1; end=end1; } } else { sum1=0; } i++; } } else i++; } cout<<"Start: "<<start<<endl <<"End: "<<end<<endl; for(i=start;i<=end;i++) cout<<ip[i]<<" "; cout<<endl <<"The sum is "<<sum<<endl; } int main() { int a[10]={2,-3,4,-3,2,2,-2,1,4,-3}; MaxSum(a,10); return 0; }[/code:1:c280388c1b] |
| whpu000625 回复于：2005-01-08 14:22:48 |
| 呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的 |
| aero 回复于：2005-01-08 19:34:07 |
| yuxh提出的算法不就是O（n）的吗？ |
| lisp 回复于：2005-01-08 19:49:48 |
| [quote:d3f80313e3="whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法[/quote:d3f80313e3]
呵呵，表示怀疑 |
| guile 回复于：2005-01-08 20:02:46 |
| [quote:f58c1b2c0e="whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的[/quote:f58c1b2c0e]
真的吗？那我心情好受一些，当时我可是本来想自己做出来，想了一下午还是不对，看了yuxh的算法才算弄懂。 总之打击很大，第二天花100多块钱买了两本算法书...这样说的话我便舒心多了，不过更佩服yuxh了 |
| assiss 回复于：2005-01-08 20:07:01 |
| 怎么可能啊。骗小孩的，guile也相信？ |
| guile 回复于：2005-01-08 20:22:48 |
| [quote:c5b75bf7b9="assiss"]怎么可能啊。骗小孩的，guile也相信？[/quote:c5b75bf7b9]
唔，还是等眼见为实。如果whpu000625能给出出处我便信了。 |
| cattiger 回复于：2005-01-09 09:47:04 |
| 阅读了yuxh的算法，改造了一下，使逻辑统一一下：
各位验证一下 [code:1:e286e83fa5]#include <stdio.h> void MaxSum(int *ary, int n) { int i, start=0, end=0, start1=0, max, sum; max=sum=ary[0]; for(i=1; i<n; i++) { if(ary[i] > 0 && sum <= 0) { start1 = i; } sum += ary[i]; if(sum<0) { start1=i; } if (sum > max) { start = start1; end = i; max = sum; } else if(sum < 0) { sum = 0; } } printf("start %d, end %d, sum %d\n", start, end, max); } void main() { int m[10] = {2, 3, -6, 3, 4, 3, -7, 5, 3, -3}; MaxSum(m, 10); return; }[/code:1:e286e83fa5] |
| eagerly1 回复于：2005-01-09 14:17:57 |
| [quote:ebc5edec10="cattiger"]
[/quote:ebc5edec10][code:1:ebc5edec10]if(ary[i] > 0 && sum <= 0) { start1 = i; } sum += ary[i]; [/code:1:ebc5edec10] 似乎应该为：[code:1:ebc5edec10]if(ary[i] > 0 && sum <= 0) { start1 = i; sum=0; } sum += ary[i]; [/code:1:ebc5edec10] |
| yuxh 回复于：2005-01-09 17:34:14 |
| 楼上说得没错
int m[10] = {-3, -1, -6, -3, -4, -3, -7, -2, -3, -3}; 所以 [quote:81b92bcdea="assiss"]我觉得把负数单独拿出来考虑更好一点[/quote:81b92bcdea]也是有道理的 |
| win_hate 回复于：2005-01-09 23:59:36 |
| 因为 yuxh 的精彩算法，此贴评为精彩。 |
| win_hate 回复于：2005-01-10 00:22:58 |
| 我对这个问题作一个简单分析：
一串正负(零)交替的数，把相邻的正数合并求和，把相邻的负数也合并求和，零可分到任何一组当中，得到如下的形式: 1) +A_1, -A_2, +A3, -A4, ...... 2) -A_1, +A_2, -A3, +A4, ...... 先讨论（1）， A_1 记录为当前最大和。如果 A_1 - A_2 <= 0, 则 ，A_1, -A_2 丢弃，从 A_3 重新计算。否则， A_1 - A_2 + A_3 为当前最大和，依此类推。 再讨论 (2) 如果合并后的序列仍有多项，则 －A_1 可丢弃，从 A_2 开始讨论，这样就归结到了情形（1）。如序列中只有一项（原序列非正），可区别对待，相当于序列求最大值。 实现： 出于对效率的考虑，我们不能把 A_i 一一求出，可用如下方法： a) 如果开始有负数，现求出这段负数（0）的最大值，并记录。 b) 如果序列未结束，用一个临时变量对后面的一段正数（0)求和，并取代原最大值（最后一次取代）。 c) 如果序列仍未结束，把后一段的负数（0）依次加到该临时变量中。一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。求和的临时变量设为0。如果把该段负数累加完后，临时变量仍不为负，则可再与其后的正数段相加 ...... 本人的一个实现： .h [code:1:d4a9ffclearcase/" target="_blank" >ccfa] struct lms { int l; int r; int sum; }; [/code:1:d4a9ffccfa] .c [code:1:d4a9ffccfa] void lms(int *tag, int len, struct lms *info) { int sum, tmp, r, l = 0; for (r = 0; tag[r] <= 0 && r < len; r++) { l = (tag[l] < tag[r]) ? r : l; } info->l = info->r = l; info->sum = tag[info->l]; l = r; sum = 0; while (r < len) { for (; r < len && tag[r] >= 0; r++) sum += tag[r]; if (sum > info->sum) { info->sum = sum; info->l = l; info->r = r - 1; } for (; r < len && tag[r] <= 0; r++) { if ((sum += tag[r]) < 0) { for (; r < len && tag[r] <= 0; r++); if (r < len) { sum = 0; l = r; } r--; } } } } [/code:1:d4a9ffccfa] |
| feingnord 回复于：2005-01-10 03:23:03 |
| 如果两个相邻元素是最大的，那和肯定是最大的，这么考虑so simple,
但是相邻这个概念就太模糊，就像二楼恩个一块相邻那种理解也说得过去， 但是超过两个，其中某些元素说自己和其它元素都相邻，揍有点不大对劲。 这种出题方式会把一些逻辑严密思维清晰的人给整死的。嘿嘿 |
| ericooler 回复于：2005-01-13 11:45:08 |
| 看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11: |
| win_hate 回复于：2005-01-13 11:58:25 |
| [quote:97e96fa894="ericooler"]看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11:[/quote:97e96fa894]
我贴出来的是 yuxh 的算法，不是我想出来的。 |
| cattiger 回复于：2005-01-13 12:17:25 |
| [code:1:59c251eeee]#include <stdio.h>
void MaxSum(int *ary, int n) { int i, start=0, end=0, start1=0, max, sum; max=sum=ary[0]; for(i=1; i<n; i++) { if(sum < 0) { sum = 0; } if((sum==0&&ary[i]>0)||ary[i]>max) { start1=i; } sum += ary[i]; if (sum > max) { start = start1; end = i; max = sum; } } printf("start %d, end %d, sum %d\n", start, end, max); } void main() { int m[10] ={-2,-3,-6,-3,-4,-3,-2,-1,-2,-3};//{2,3,-6,3,4,3,-2,5,2,-3}; // {-3, -1, -6, 0, -4, -3, -7, -2, -3, -3};// MaxSum(m, 10); return; }[/code:1:59c251eeee] |
| eagerly1 回复于：2005-01-13 18:15:48 |
| [quote:95f5a89724]一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。[/quote:95f5a89724]
这样一来，起点就会失去吧。除非判断时记录 |
| zouyuchong 回复于：2005-07-31 18:59:20 |
| 用线段树做
或者转换成RMQ问题 |
| sasnzy12 回复于：2005-08-06 20:47:53 |
| 比较简单的贪心吧~~（如果贪心不能理解的话 用动态规划好了）
贪心就是把正数与正数合并 负数与负数合并 如果是0就不要 形成一个交错数列 （该数列头尾必须是正数，如果是负数则删除） 然后从头开始 //result是合并以后的交错数列 max=result[0]; (result[0]是正数,result[result.size()-1]也是正数 for (int i=2;i<result.size()-2;i+=2) max=(result[i]>max+result[i-1]+result[i] ? result[i] : max+result[i-1]+result[i]) //OK cout<<max<<endl; 贪心 o(N) （编程相对复杂） 动态规划O(N^2) （10代码行解决问题） 居然还要线段树 ？ %#$%#$%# |
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-
