最大子段和问题的简洁描述是:对于给定序列[ x1,x2,x3...]寻找它的某个连续子段,使得其和最大。如{ -1,5,-2,1,-7,-4,2,3,-1,2 }最大子段是{ 2,3,-1,2 }其和为6。这个问题可以从枚举、分治、动态规划,贪心这几个角度来解。
(1)枚举解法思路:对于数组a[n],其连续的子段有
以a[0]开始的 , { a[0] }, { a[0],a[1] },{ a[0],a[1],a[2] }.....共n 个
以a[1]开始的, { a[1] }, { a[1],a[2] },{ a[1],a[2],a[3] }.....共n-1个
...
以a[n]开始的,{ a[n] }共1个
一共(n+1)......
阅读全文