最大子序列和

四个算法求解最大子序列和问题

算法1：

 1 int MaxSubsequenceSum_1(const int a[] , int n)
 2 {
 3     int ThisSum , MaxSum , i , j , k ;
 4     MaxSum = 0 ;
 5     for(i = 0 ; i < n ; i ++)
 6     {
 7         for(j = i ; j < n ; j ++)
 8         {
 9             ThisSum = 0 ;
10             for(k = i ; k < i ; k ++)
11             {
12                 ThisSum += a[k] ;
13             }
14             if(ThisSum > MaxSum)
15                 MaxSum = ThisSum ;
16         }
17     }
18     return MaxSum ;
19 }

分析：

穷举法,该算法肯定会正确运行，运行时间为O(N³)，这完全取决于第10行和第12行，第12行由一个含于三重嵌套for循环中的O（1）语句组成第5行上的循环大小为n。第2个循环大小为n-i，他可能要小，但也可能是n。我们必须假设最坏的情况，而这可能会使得最终的界有些大，第三个循环的大小为j-i+1，我们也要假设它的大小为n。因此总数为O（1^.N^.N^.N）=O(N³).

我们可以通过撤除一个for循环来避免立方运行时间，可以看出算法1在第10行12行过分的耗时了

算法2：

 1 /*穷举法，减去了一些不必要的操作，通过撤除一个for循环来避免立方运行时间，运行时间为O(N^2)*/
 2 int MaxSubsequenceSum_2(const int a[] , int n)
 3 {
 4     int ThisSum , MaxSum , i , j ;
 5     MaxSum = 0 ;
 6     for(i = 0 ; i < n ; i ++)
 7     {
 8         ThisSum = 0 ;
 9         for(j = i ; j < n ; j ++)
10         {
11             ThisSum += a[i] ;
12             if(ThisSum > MaxSum)
13                 MaxSum = ThisSum ;
14         }
15     }
16     return MaxSum ;
17 }

分析：虽然和算法1一样是穷举法，但是在算法1中会计算很多不必要的工作，例如当i = 0, j = 3时，会计算a[0] + a[1] +…+ a[3]；而当i = 0, j = 4时候又会计算a[0] + a[1] +…a[4]。

通过撤除一个for循环，使得算法的时间复杂度为O(N²).

算法3：

 1 static int MaxSubSum(const int a[] , int left , int right)
 2 {
 3     int MaxLeftSum , MaxRightSum ;
 4     int MaxLeftBorderSum , MaxRighBorderSum ;
 5     int LeftBorderSum , RightBorderSum ;
 6     int Center , i ;
 7     if(left == right)  //如果left = right ，那么只有一个元素，并且当该元素非负时它就是最大和子序列
 8     {
 9         return a[left] ;
10     }
11     else
12         return 0 ;
13     Center = (left + right) / 2 ;
14     MaxLeftSum = MaxSubSum(a , left , Center) ;
15     MaxRightSum = MaxSubSum(a , Center , right) ;
16     MaxLeftBorderSum = 0 ;
17     LeftBorderSum = 0 ;
18     for(i = Center ; i >= left ; i --)
19     {
20         LeftBorderSum += a[i] ;
21         if(LeftBorderSum > MaxLeftBorderSum)
22             MaxLeftBorderSum = LeftBorderSum ;
23     }
24     MaxRighBorderSum = 0 ;
25     RightBorderSum = 0 ;
26     for(i = Center + 1 ; i < right ; i ++)
27     {
28         RightBorderSum += a[i] ;
29         if(RightBorderSum > MaxRighBorderSum)
30             MaxRighBorderSum = RightBorderSum ;
31     }
32     return Max3(MaxLeftSum , MaxRightSum , MaxLeftBorderSum + MaxRighBorderSum) ;
33 }
34 int Max3(int a, int b, int c)
35 {
36        if (a < b)
37        {
38               a = b;
39        }
40        if (a > c)
41               return a;
42        else
43               return c;
44 }
45 int MaxSubsequenceSum_3(const int a[] , int n)
46 {
47     return MaxSubSum(a , 0 , n -1) ;
48 }

算法描述：该算法采用了一种“分治（divide-and-conquer）”策略，其想法是把问题分成大致相等的子问题，然后递归的对他们求解，这是“分”部分；“治”阶段将两个子问题的解合并到一起并可能在做些少量的附加工作，最后得到整个问题的解。
分析：最大子序列和可能在三处出现。或者整个出现在输入数据的左半部，或者整个出现在右半部，或者跨越输入数据的中部从而占据左右两半部分。前2种情况可以递归求解，第三种情况的最大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素）而得到，然后将这两个和加在一起。令T（N）是求解大小为N的最大子序列和所花费的时间。第16到31行花费的时间是O（N），第14、15行是求解大小为N/2的子序列问题（假设N为偶数），其余工作量为常量，所以T(N)=2T(N/2)+O(N)，又知T（1）=1，两式联立克制T(N)=O(NlogN)。
算法4：

 1 int MaxSubsequenceSum_4( const int a[] , int n)
 2 {
 3     int ThisSum , MaxSum , j ;
 4     ThisSum = MaxSum = 0 ;
 5     for( j = 0 ; j < n ; j ++)
 6     {
 7         ThisSum += a[j] ;
 8         if(ThisSum > MaxSum)
 9             MaxSum = ThisSum ;
10         else if(ThisSum < 0)
11             ThisSum = 0 ;
12     }
13     return MaxSum ;
14 }

分析：

很容易理解时间界O(N) 是正确的，但是要是弄明白为什么正确就比较费力了。其实这个是算法2的一个改进。分析的时候也是i代表当前序列的起点，j代表当前序列的终点。如果我们不需要知道最佳子序列的位置，那么i就可以优化掉。

重点的一个思想是：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀。例如说，循环中我们检测到从a[i]到a[j]的子序列是负数，那么我们就可以推进i。关键的结论是我们不仅可以把i推进到i+1，而且我们实际可以把它一直推进到j+1。

举例来说，令p是i+1到j之间的任何一个下标，由于前面假设了a[i]+…+a[j]是负数，则开始于下标p的任意子序列都不会大于在下标i并且包含从a[i]到a[p-1]的子序列对应的子序列（j是使得从下标i开始成为负数的第一个下标）。因此，把i推进到j+1是安全的，不会错过最优解。注意的是：虽然，如果有以a[j]结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与a[j]后面的数形成的最大子序列的开头，但是并不表明a[j]前面的某个序列就不是最大序列，也就是说不能确定最大子序列在a[j]前还是a[j]后，即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。这个算法还有一个有点就是，它只对数据进行一次扫描，一旦a[j]被读入处理就不需要再记忆。它是一个联机算法。

联机算法：在任意时刻算法都能够对它已读入的数据给出当前数据的解。

常量空间线性时间的联机算法几乎是完美的算法。

 参考文献：《数据结构与算法-C语言描述》 机械工业出版社
 参考博客：http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html