Re: [討論] 面試遇到的考題
※ 引述《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
又是一題線性DP題 這次懶得寫code了 直接弄演算法 免得又要爭那實作效率
假設題目輸入的是a[1]~a[n]
初始化： b00[0], b01[0], b10[0], b11[0] 都設為0
b後面兩個數代表前兩項有沒有取 而該數值為該狀況下的最大值
因為題目只說整數(可能有負的) 所以b00保留
推廣：
b00[i] = max of b00[i-1], b10[i-1]
b01[i] = max of b00[i-1]+a[i], b10[i-1]+a[i] 實際上就是b00[i]+a[i]
b10[i] = max of b01[i-1], b11[i-1]
b11[i] = b01[i-1]+a[i] 由於b11[i-1]+a[i]的狀況會造成連續選三個 忽略之
答案：
ans = max of b00[n], b01[n], b10[n], b11[n]
每一層四個b數值都是可丟棄的
如果覺得開個陣列很浪費寶貴的空間
可以直接蓋掉舊的
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.4.157
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1405101677.A.1A0.html
推
07/12 06:42, , 1F
07/12 06:42, 1F
→
07/12 06:43, , 2F
07/12 06:43, 2F
討論串 (同標題文章)