最大连续子序列和：动态规划经典题目(2)

问题描述：

      连续子序列最大和，其实就是求一个序列中连续的子序列中元素和最大的那个。

      比如例如给定序列：

           { -2, 11, -4, 13, -5, -2 }

        其最大连续子序列为{ 11, -4, 13 }，最大和为20。

===============================================================

问题分析：

1.首先最朴素的方法是暴力 O(n^3)

       直接两个for循环枚举子序列的首尾，然后再来个循环计算序列的和，每次更新和的最大值。

        但是这种方法的复杂度是O(n^3)，效率实在太低了。。。

————————————————————————————————————————————————

2.第二种方法是预处理 O(n^2)

       在读入的时候将前面数的和放在数组中，就能得到一个数组sum[i]储存前i个数的和。然后两重循环枚举首尾，利用sum数组迅速求出子序列的和。

        其实这种方法只是优化了前面那种方法的计算和的循环，复杂的是O(n^2)，也很糟糕。
————————————————————————————————————————————————

3.第三种是利用分治思想 O(nlogn)

      分治算法但看代码不是很好理解，其实思想很简单，就是把序列分成两块计算，用递归分别求出两块序列中的最大子序列和，然后从序列中间向两边遍历求出包含中心的序列的最大和。返回最大的那个序列和。

       递归真的很神奇，一直把问题分解乘小问题交给下一层递归处理，直到最底层。

       用分治算法的复杂度好了一些，是O(nlogn)，虽然不是最优解，但是理解这种算法的确能让我们对递归理解得更加深刻。
————————————————————————————————————————————————

4.第四种是累积遍历算法 O(n)

      遍历序列的时候对Sum进行累计，如果Sum累积后小于0的话就把Sum重置为负无穷，每次更新Sum的最大值。最后便能求出最大值。

       其实这个算法就是把序列分为好几块，每一块满足：对于任意k，前k个数的和不会小于0（小于0就会分裂成两块了），当前i个数的和大于最大值时就进行更新，而最大值的左边界就是该块序列的第一个，右边界是第i个。

       时间复杂度为O(n)，而且可以一边读取一边处理，不需要开辟数组来存，空间也很省。

------------------------------------------------------------------------------

   举个例子: 

-10   1  2  3  4  -5   -23   3  7    -21   (num)

-10 | 1  3  6 10  8 | -23 |  3 10 | -21   (Sum)（|号为该处Sum被清零）

   由于10是Sum的最大值，所以，红色的那块就是要求的范围了。

------------------------------------------------------------------------------

     但是为什么所求序列为什么是在序列块中并且是以序列块第一个数作为开头呢？

证明：如果不是这样的话，会有几种情况：

          1  该目标序列跨越了几个块。由于Sum在<=0的时候会重置为负无穷，如果跨块的话，没有重置那它的和肯定不会是最大的。

          2  该目标序列在序列块中间，且目标序列的开头并不是序列的第一个。由于序列块前k个数的和不会小于0，所以这样肯定没有从第一个开始来的大。

————————————————————————————————————————————————

5.第五种是动态规划 O(n)

        dp做法是很普遍的做法，只要想出状态转移方程就可以很快做出来了。

        状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大连续和。)在dp的过程中便可以更新sum数组的最大值以及两个边界。

        其实完全可以不用开数组，累计sum直到sum + a < a，把sum赋值为a，更新最大值就行了。你会发现这跟第4种方法是一样的。。。只是判断条件不一样，一个是sum <= 0一个是sum + a < a。。。（其实是一样的。。。）所以复杂度和第四种是一样的都是O(n)。

————————————————————————————————————————————————

6.第六种是第二种累计求和 O(n)

       （感谢@shuangde800 大神的指导）

         这种方法跟第4种一样是累计求和。我们可以发现，连续子序列的和其实就是 （到尾端的和）-（到首端-1的和），要让这个式子最大其实可以让（到首端-1的和）尽量的小，我们可以遍历数组，维护（到首端-1的和）的最小值。

         理解起来就是遍历的时候，找出以当前位置为尾端，以此前的某一点为首端的 和最大的子序列，然后更新最大值。（其实这个思想和第五种方法是异曲同工的）

         由于只需要一遍遍历，所以复杂度为O(n)。

===============================================================

伪代码:

由于下面的Solution里面我的代码太挫，于是先贴出伪代码。

1.暴力 O(n^3)：

[plain] view plain copy  print?

1. max←(-∞)  
2. for i←1 to len do  
3.     for j←i to len do  
4.         sum←0  
5.         // 求和  
6.         for k←i to j  
7.             sum←sum+arr[i]  
8.         end for  
9.         // 更新最大值  
10.         if sum>max then  
11.             max←sum  
12.         end if  
13.     end for  
14. end for  
15. return max  

2.预处理 O(n^2)：

[plain] view plain copy  print?

1. // 记录前i项和  
2. sum[0]←0  
3. for i←1 to len do  
4.     sum[i]←sum[i-1]+arr[i]  
5. end for  
6. // 枚举首尾  
7. max←(-∞)  
8. for i←1 to len do  
9.     for j←i to len do  
10.         // 更新最大值  
11.         if sum[j]-sum[i-1]>max then  
12.             max←sum[j]-sum[i-1]  
13.         end if  
14.     end for  
15. end for  
16. return max  

3.分治算法 O(nlogn)

[plain] view plain copy  print?

1. function maxsum(arr,left,right)  
2.     // 只有一个元素就返回  
3.     if right-left=1 then  
4.         return  
5.     end if  
6.     // 划分[left,mid)和[mid,left)分治  
7.     mid←x+(y-x)/2  
8.     L←maxsum(arr,left,mid)  
9.     R←maxsum(arr,mid,left)  
10.     if L>R then  
11.         max←L  
12.     else  
13.         max←R  
14.     end if  
15.     // 求出处于中间的连续子序列最大和  
16.     // 先求从中间向左最大值  
17.     tempSum←0  
18.     leftSum←arr[m-1]  
19.     for i←m-1 downto right do  
20.         tempSum←tempSum+arr[i]  
21.         if leftSum<tempSum then  
22.             leftSum←tempSum  
23.         end if  
24.     end for  
25.     // 再求从中间向右最大值  
26.     tempSum←0  
27.     rightSum←arr[m]  
28.     for i←m to left do  
29.         tempSum←tempSum+arr[i]  
30.         if rightSum<tempSum then  
31.             rightSum←tempSum  
32.         end if  
33.     end for  
34.     midSum←leftSum+rightSum  
35.     if max<midSum then  
36.         max←midSum  
37.     end if  
38.     return max  
39. end function  

4.累积遍历算法 O(n)

[plain] view plain copy  print?

1. sum←0  
2. max←arr[0]  
3. for i←1 to len do  
4.     if sum<=0 then  
5.         sum←a[i]  
6.     end if  
7.     if max<sum then  
8.         max←sum  
9.     end if  
10. end for  
11. return max  

5.动态规划 O(n)

[plain] view plain copy  print?

1. sum←(-∞)  
2. max←(-∞)  
3. for i←1 to len do  
4.     if sum+arr[i]<arr[i] then  
5.         sum←arr[i]  
6.     else  
7.         sum←sum+arr[i]  
8.     end if  
9.     if max<sum then  
10.         max←sum  
11.     end if  
12. end for  
13. return max  

6.第二种累计求和 O(n)

[plain] view plain copy  print?

1. max←-INF  
2. recMin←0  
3.   
4. for i←1 to len do  
5.     sum←sum+arr[i]  
6.     temp←sum-recMin  
7.     // 更新max  
8.     if temp>max then  
9.         max←temp  
10.     end if  
11.     // 更新recMin  
12.     if recMin>sum then  
13.         recMin←sum  
14.     end if  
15. end for  

===============================================================

Solution:

hdu这两题都是要求边界的。

代码如下：

hdu 1003:

       题意：求出给出序列中和最大的连续子序列，以及该序列的左边界和右边界

 累积遍历算法（会TLE）

[cpp] view plain copy  print?

1.  /* 
2.  *   Author:        illuz <iilluzen@gmail.com> 
3.  *   Blog:          http://blog.csdn.net/hcbbt 
4.  *   File:          3.cpp 
5.  *   Lauguage:      C/C++ 
6.  *   Create Date:   2013-08-28 01:12:27 
7.  *   Descripton:    max sum of continuous sequence, simulation  
8.  */  
9. #include <cstdio>  
10. #define rep(i, n) for (int i = 0; i < (n); i++)  
11.    
12. const int MAXN = 100100;  
13. int k, a[MAXN];  
14.   
15. int main() {