Re: [討論] 令人印象深刻的遞迴問題？
※ 引述《yauhh (喲)》之銘言：
: 我的作法是純粹累加差值,看哪個累計差值最高,就可以把左邊界推到最極限.
: 然後在左邊界可以往前推的前提下,看看右邊界可不可以往前推.
: 我的左邊界就是低點,右邊界就是高點,因為遞迴的關係,所以是先從陣列右邊開始算,
它「應」是對的，之前看過之「類似」題：
Q : 給定一整數數列，有正有負，ex: [3 2 8 9 -25 5 8 4 4 -3 5 3 -10]
要求「連續最大總合」之其合應為多少？若連續最大總合 <=0 則輸出 0
ex1: 3+2+8 = 13
ex2: 5+8+4 = 17
ex3: 5+8+4+...+3=26(max)
-----
sol:
(1) 一個一個慢慢掃
(2) 當 cur_sum < 0 時，將 cur_sum 歸 0，正值時累加
(3) 若 cur_sum > max_sum，取代
num 3 2 8 9 -25 5 8 4 4 -3 5 3 -10
cur_sum 3 5 13 22 0(-3) 5 13 17 21 18 23 26 16
max_sum 3 5 13 22 22 22 22 22 22 22 23 26 26
----
coding:
for(i=0; i!=sizeof(array)/ sizeof(int); ++i){
cur_sum+=array[i];
if(cur_sum<0) cur_sum=0;
if(cur_sum>max_sum) max_sum = cur_sum;
}
printf("%d\n", max_sum);
----
lemma1: 第一次看到原題時, 聯想到是這題，直覺是和 yauhh 相同做法。
lemma2: 這題有進階題, 有待討論 (也不難解) : 若為 cicle link 非 array？
lemma3: 這題在「教育部資訊軟體人才培育先導計畫」第二次競賽裡面似乎也有
http://algorithm.csie.ncku.edu.tw/ETPC/
lemma4: purpose 所提供之題目，「似乎」是將程式碼再紀錄
start_max_pos, end_max_pos，「加以變型」後可得，不知是否有意會錯。
lemma5: 吾人 power 不夠，實在想不透如何限定用 recursive 實做。
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.72.67
※ 編輯: tropical72 來自: 180.177.72.67 (04/01 17:55)
推
04/01 17:55, , 1F
04/01 17:55, 1F
→
04/01 21:28, , 2F
04/01 21:28, 2F
→
04/01 21:30, , 3F
04/01 21:30, 3F
→
04/01 21:31, , 4F
04/01 21:31, 4F
→
04/01 21:31, , 5F
04/01 21:31, 5F
→
04/01 21:38, , 6F
04/01 21:38, 6F
→
04/01 21:48, , 7F
04/01 21:48, 7F
→
04/02 12:58, , 8F
04/02 12:58, 8F
→
04/02 12:58, , 9F
04/02 12:58, 9F
討論串 (同標題文章)