推 sevenpu:感謝耶~~~可是還有有些不太懂! 01/05 18:11
→ sevenpu:可以在說明清楚一點嗎!!!拜託~~ 01/05 18:12
※ 引述《sevenpu (pu)》之銘言：
: 想請問第二頁的第六題
: http://www2.lib.nctu.edu.tw/n_exam/exam95/iim/iim5092.pdf
: 想請問要怎麼解
: 昨天在這裡想了好久還是解不出來
: 希望有人能幫幫忙喔
: 謝謝^^
把陣列分成長度相等的前後兩半
分別求出前半與後半的 Maximum Sum (所有元素都在內部)
Maximum Prefix Sum (由頭部開始的)
Maximum Suffix Sum (結束在尾端的)
那自己的Maximum Sum = Max(左半Maximum Sum, 右半Maximum Sum,
左半Suffix加右半Prefix)
Maximum Prefix Sum = Max(左半Maximum Prefix Sum,
左半全部 + 右半Maximum Prefix Sum)
Maximum Suffix Sum = Max(右半Maximum Suffix Sum,
右半全部 + 左半Maximum Suffix Sum)
遞迴關係是T(n) = 2T(n/2) + O(1) = O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50