模板
教程
環境
性能
功能
管理
求一個數組中最大的相鄰元素之和
求一個數組中最大的相鄰元素之和 舉例： 數組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代碼行解決問題） 居然還要線段樹 ？ %#$%#$%# |
- 評論列表（網友評論僅供網友表達個人看法，并不表明本站同意其觀點或證實其描述）
-
