Re: [討論] 令人印象深刻的遞迴問題？

[tropical72 (藍影)]

※ 引述《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)
推 attomahawk:推 Lemma。數學模型慢慢出來，感覺可以做小論文了！
→ yauhh:我第一次看到直覺並不是這樣的作法,而是比較慢比較穩的分解
→ yauhh:法. 基本是先對每個數字找到另一個數字,是右邊最高點;然後
→ yauhh:是每個數字跟另一個數字取差值,然後找最大的.我比較重視有
→ yauhh:意義的解題步驟.
→ tropical72:@yauhh:或許應先將此題轉至Programming討論適合些:)
→ loveme00835:感覺就是partial sum的應用囉
→ yauhh:本來是有解題板可以討論,但是大家都寫C/C++會開始想題目怎解
→ yauhh:所以自然會有些演算法討論出現在這種板上