最大子数组连续和问题(数组为环)

3056阅读　1评论2012-09-08　datao0907
分类：C/C++

编程之美中2.14的扩展为数组为环的情况下，最大连续和的求解问题，这里给出的答案出现了错误，其中谈到有环的情况，求以A[0]开头的最大连续和(A[0]......A[j])，并求以A[n-1]为尾的最大连续和(A[i],....,A[n-1]),在讨论时，出现 i <= j,则最大连续和为A[0] ..... A[n-1],这里有钟情况未进行处理：

假设数组为:5 -3  -1 5 10 11
以A[0]为头的最大连续和为5 -3 -1 5 10 11,以A[n-1]结尾的和也是该序列，但是由于出现环，最大连续和却是:5 10 11 5,这里对其进行修改，提出另外一种算法:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*
  4.  * 现在是数组为一个环形结构，最大连续和又该如何实现?
  5.  * 1.最简单的方法：数组循环移位，再进行逐一求解最大连续和,算法复杂度O(n^2)
  6.  * 2.s[i][l] = s[i][l-1]+a[i+l-1]; sum = max{s[i][l]},s[i][l]:以i开始长度为l的连续和
  7.  * O(n) 的解法:
  8.  * 1.解未出现跨域的情况，也就是a[0] ~ a[n-1](原问题)
  9.  * 2.解出现跨域情况 a[n-1]~a[0] 出现在解的中间或边界
  10.  */

  12. int max_subarray_bound(int a[],int from,int to)
  13. {
  14.     int i,max,sum;
  15.     
  16.     max = a[from];
  17.     sum = a[from];
  18.     
  19.     for(i = from + 1;i <= to;i++) {
  20.         if(sum < 0)
  21.             sum = 0;
  22.         sum += a[i];
  23.         if(max < sum)
  24.             max = sum;
  25.     }

  27.     return max;
  28. }


  31. int max_subarray_cycle(int a[],int size)
  32. {
  33.     int sum,i,j,s,m;
  34.     
  35.     //第一种情况,未跨域
  36.     sum = max_subarray_bound(a,0,size-1);
  37.     /*
  38.      * 第二种情况，出现跨域,既然a[0] a[n-1]都出现在解中，则可以将其解延伸到最大，
  39.      * 也就是从a[0]开始，向右扫描，从a[n-1]开始向左扫描,两者直到出现负数为止，
  40.      * 这样就不会出现中间是负数，但是两端是正数，但却选择整个序列的情况.
  41.      */

  43.     if(size == 2) return sum;

  45.     i = 1;
  46.     j = size-2;

  48.     s = a[i-1] + a[j+1];
  49.     
  50.     while(i < j && (a[i] >=0 || a[j] >= 0)) {
  51.         if(a[i] >= 0) {
  52.             s += a[i];
  53.             i++;
  54.         }
  55.         
  56.         if(a[j] >= 0) {
  57.             s += a[j];
  58.             j--;
  59.         }
  60.     }
  61.     
  62.     if(i == j) {
  63.         if(a[i] >0) s+=a[i];
  64.         if(s < sum) return sum;
  65.         else return s;
  66.     }
  67.     
  68.     if(i < j) {
  69.         //算出以i为头部的所有连续子数组和或者以j为尾的连续子数组和,从而找到最大的元素
  70.         int s2,k;
  71.         m = a[i];
  72.         s2 = m;
  73.         for(k=i+1;k <= j;k++) {
  74.             s2 += a[k];
  75.             if(m < s2)
  76.                 m = s2;
  77.         }
  78.         
  79.         s2 = a[j];
  80.         for(k = j-1;k>=i;k--) {
  81.             s2 += a[j];
  82.             if(m < s2)
  83.                 m = s2;
  84.         }
  85.         
  86.         if(m > 0)
  87.             s += m;
  88.     }
  89.     
  90.     if(s < sum) return sum;
  91.     else return s;
  92.     
  93. }


  96. int main(int argc,char *argv[])
  97. {
  98.     //int a[] = {1,-3,20,-4,-10,11};
  99.     int a[] = {5,-3,-1,5,10,11};

  101.     printf("max sub array(cycle):%d\n",max_subarray_cycle(a,sizeof(a)/sizeof(a[0])));

  103.     return 0;
  104. }
 最值问题多半采用动态规划来完成，但在分析最优化子问题需要分析子问题的前缀特点，一般来讲前缀存在的形式有如下：
 1.如果是连续问题，则前缀形成的递归式为i 与 i+1 项之间的关系
2.非连续问题，子问题就成了i 与 j之间的问题
3.如果是非连续，又有限定条件(背包问题)，就需要采用i项"选“与”不选“之间的关系，写成递归式
4.上面涉及的都是单数组之间的前缀分析，如果涉及到两个以上的数组，则定义的子问题又可上面的三种形式：
 5.子问题的前缀均为连续形式，则递归式就是每个数组之间i项与i+1项之间的关系
 6.子问题的前缀非连续形式，则递归式中就是每个数组之间的i项与j项之间的关系
 7.子问题的前缀在有限制的情况下，则递归式就是每个数组之间的i项”选“与”不选“之间的关系
上一篇：sprintf 的小问题
下一篇：一些随机算法

文章评论