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

3076阅读 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.  */

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

  25.     return max;
  26. }


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

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

  39.     i = 1;
  40.     j = size-2;

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


  87. int main(int argc,char *argv[])
  88. {
  89.     //int a[] = {1,-3,20,-4,-10,11};
  90.     int a[] = {5,-3,-1,5,10,11};

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

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

文章评论