Re: [討論] 面試遇到的考題

[lovdkkkk (dk)]

※ 引述《changyuheng (張昱珩)》之銘言：
: 加碼一題：
: 給任一有限長度整數數列，
: 求以特定方法取出其中數字加總所能獲得的極大值。
: 取法條件限制：
: 最多連續取 2 個數，亦即不得連續取 3 個數。
: 例：
:     2, 1, 9, 5, 2, 0, 1, 3, 4
: 可以下列方法取出數字：
: 1)  2, 1,    5, 2,    1, 3
: 2)  2, 1,       2, 0,       4
: 不可以下列方法取出數字：
: 1)  2, 1, 9,    2, 0,    3, 4

看不太出來這題是要考什麼 @@
好像就直接算而已。

// 喝完一瓶紅酒剛睡醒頭有點痛的爛 code
// c style, 可能不能跑...XD

int[] arr = {/* 管它是什麼 */};
int[] pos = {0, 0}, mpos = {0, 0};
int i, j, max, curr;

// 需要的話這裡先判斷 arr 是不是空的

max = arr[0];
for (i = 0; i < arr.length; i++) {
    curr = arr[i]; // 直接改掉 curr 跟 pos
    pos[0] = pos[1] = i;
    if (curr > 0) { // 目前數為正才考慮要不要加上下一個
        j = i+1;
        if (j < arr.length // 後一個不為正就忽略
            && arr[j] > 0) // 不然就給它加下去
            curr += arr[j];
            pos[1] = j;
        }
    }
    if (curr > max) { // 比大小, 更新
        mpos[0] = pos[0];
        mpos[1] = pos[1];
        max = curr;
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.148.44
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1405117016.A.1D3.html
→ robler:明明就有程式板可以討論..
→ lovdkkkk:推樓上 XD
推 summerleaves:Programming
推 changyuheng:因為也是面試題，所以才 po
→ lovdkkkk:真的是面試題 @@ 不知有沒有什麼特別的解...
推 PUTOUCHANG:很簡單啊, PO 到 programming 板或 stackoverflow 問
→ pika0923:其實是Prob_Solve版的業務 那邊有很多好玩的面試題
→ pika0923:是說以這篇來說我的作法似乎對題目的解讀錯誤?
→ pika0923:以為說可以取超過一個區段 每段長度最大2
→ pika0923:這篇好像是作單一區段?
→ lovdkkkk:嗯嗯, 原題有說連續, 舉的能取的例子也都是連續的
→ pika0923:是說這樣2,1的區段還要拿兩個例子來講還蠻特別的XD
推 changyuheng:抱歉是我不夠仔細，題意是多個區段加總。與討論串原
→ changyuheng:題屬於同樣的演算法也同是面試題 (年薪一百上下，當
→ changyuheng:時是要求當場口頭回答)。解答根據前同事所教，在取
→ changyuheng:每一個數時，都考慮不取的答案、和取了屬於區段第一
→ changyuheng:和第二個數的的答案，即可透過帶著三個數 O(n) 求得
→ changyuheng:。
→ lovdkkkk:看到修改後的了, 那 "多個" 有限制幾個嗎? 看舉例都是三
→ lovdkkkk:個區段 @@
→ lovdkkkk:啊, 不過幾個區段差距應該不大, 解法一樣
推 changyuheng:不限區段數目，取法只要符合條件即可。
→ pika0923:帶三個數的話應該就我那個作法拔掉b00這樣
推 changyuheng:樓上確實是 O(n) DP 解！
→ lovdkkkk:結果我是搞錯題意, 還覺得怎麼那麼簡單...XDrz