作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-交大95-资管所
时间Tue Jan 5 16:18:49 2010
※ 引述《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
1F：推 sevenpu:感谢耶~~~可是还有有些不太懂! 01/05 18:11
2F：→ sevenpu:可以在说明清楚一点吗!!!拜托~~ 01/05 18:12