问题描述 ：

从一组数字中，找出其所有连续子序列中，和数（子序列所有数字求和）最大的连续子序列：

如：数组 int A[ ] = {-4 , 3 , 5 , -1};找出某几个连续的子序列其和最大。比如A0+A1 = -1 。A1+A2+A3+A4 = 3。而A2+A3=8;则A2 A3组成的数组即是所求。

 

求解方法1：

先写我自己的方法，不是动态规划，复杂度大概是O（n*n);

1,二维数组ret[ ][ ];用上面的例子中数组A[ ]= {-4 , 3 , 5 , -1}为例：

        ～  -4   3   5   1

0        0   0   0   0   0     //为了方便计算，第0行第0列均设为0

1        0  -4   3   5   1     //第1行表示子串长度为1时，包含该位置元素的子序列和数

2        0       -1   8   6     //第2行表示子串长度为2时，包含该位置元素的子序列和数

3        0             4   9

4        0                  5

其中，ret[i][j]位置的值为ret[i-1][j-1] + inp[j-1];

原理是，包含某个数x的子串长度为k的最大和数，等于x加上x之前的子串长度为k-1的最大和数;

即：上表中ret[4][5]=4,它是子序列长度为3，包含j=5处元素（即inp[4])的最大和数，是第5列以前的所有子序列长度为3-1=2的序列中，最大和数+该位的值：ret[3][4] + inp[4]=-1+5=4;

也就是说子序列长度为i的包含第j个位置的最大和数，是基于子序列长度为i-1的j前面的最大和数来求得的;

#include
     
      #include
      
       #define MAX 100 int ret[MAX][MAX] = {
   {
   0}};//len+1行len+1列int maxSubSeqSum(int inp[],int len){        int maxret = 0;//最大的顺序子串和的值        int i = 1;//第0行和第0列都为0        for(;i
       
         maxret) maxret = ret[i][j];                        printf("ret[%d][%d]=%d\n",i,j,ret[i][j]);                }        }        return maxret;}int main(){        int input[] = {
   1,-1,4,-3,2};        int len = sizeof(input)/sizeof(int);        int ret = maxSubSeqSum(input,len);        printf("max sub sequence sum is:%d\n",ret);        return 0;}
       
      
     

 

运行结果：

xu@xu-ThinkPad-X61:~/algorithm$ gcc maxSubSeqSum.c

xu@xu-ThinkPad-X61:~/algorithm$ ./a.out

ret[1][1]=1

ret[1][2]=-1

ret[1][3]=4

ret[1][4]=-3

ret[1][5]=2

ret[2][2]=0

ret[2][3]=3

ret[2][4]=1

ret[2][5]=-1

ret[3][3]=4

ret[3][4]=0

ret[3][5]=3

ret[4][4]=1

ret[4][5]=2

ret[5][5]=3

max sub sequence sum is:4

 

 

求解方法2：

1，递归公式：f(n)表示包含元素A(n)的最大子序列和，它的最大值，要么=A(n)，要么=

A(n)+f(n-1);

2，复杂度为O(n);

#include
     
      #include
      
       #define max(a,b) (a>b)?a:bint maxSubSeqSum(int inp[],int inplen){        int presum=*inp,ret=0,i=1;//ret为最大和，presum是f(n-1)的值        for(;i
       
         ret) ret=tmpmax;        }        return ret;}int main(){        int input[]={
   1,-1,4,-3,2};        int length = sizeof(input)/sizeof(int);        int ret =maxSubSeqSum(input,length);        printf("result is:%d\n",ret);        return 0;}
       
      
     

xu@xu-ThinkPad-X61:~/algorithm$ ./a.out

result is:4

（回过头来看以前的代码，方法2其实不对，后续改进）

扫描算法（O（n））

 

1，递归公式：f(n)表示包含元素A(n)的规模为x[0…n]的问题。如何扩展为包含A(n+1)的规模为x[0…n+1]的问题f(n+1)？

2，我们用类似分治算法的原理：前i个元素中，最大总和子数组要么在前i个元素中，要么其结束位置为i+1；

    举个例子：

  int A[ ] = {-4 , 3 , 5 , -1};

      tmp = {  0 , 3 , 8 ,  7} 其中tmp = Max( tmp + A[i] , 0)

      max = {  0 , 3 , 8 ,  8} 其中max = Max(max, tmp);

tmp：从左往右扫描，第i位存的是包含第i位的最大子数组的和，如果和数小于0则存0；

max：从左往右扫描，第i位之前最大子数组的和，这个子数组可以不包含i；说白了就是第i位存i左侧所有tmp的最大值；

最终，max的最后一位8，即为和最大的连续子序列

下面看看代码：

#include 
     
      #include 
      
       #define max(a,b) a>b?a:bint fun(int A[],int n){  int i=1,maxret=0,tmp=max(A[0],0);  for(;i
      
     

[root@admin Desktop]# ./a.outtmp=7,    maxret=7tmp=8,    maxret=8tmp=2,    maxret=8tmp=0,    maxret=8tmp=9,    maxret=9tmp=11,    maxret=11tmp=10,    maxret=1111

 

 

方法3：

最简单的思路，遍历所有子序列，找出其中最大的；

int A[] = {
   31,-41,59,26,-53,58,97,-93,-23,84}; int fun(int A[], int n){   int max = 0,i = 0;   for(i=0;i
     
      max) max=tmpsum;      }   }   return max;}void main(){   int ret = fun(A,10);   printf("%d",ret);}
     

Output:187

 

方法4：

分治算法解决方案：解决规模为n的问题，可以递归地解决规模近似为n/2的子问题，然后对答案进行合并，得到整个问题的答案；

把int A[] = {31,-41,59,26,-53,58,97,-93,-23,84};

分为：31,-41,59,26,-53,

         58,97,-93,-23,84

两个子问题Sa，Sb；

现在，最大子向量必定在Sa，Sb或者跨越Sa和Sb之间边界的部位Sc；

我们分治递归Sa，Sb，并通过类似方法3的遍历的方式计算Sc；

代码如下：

#define Max(a,b,c) ((a>b?a:b)>c?(a>b?a:b):c)int A[] = {
   31,-41,59,26,-53,58,97,-93,-23,84};//divide-and-conquer algorithmint fun(int A[], int low, int high){   int mid=(low+high)/2;   int tmp=0,lret=0,rret=0,i=mid,j=mid+1;   if(low>high) return 0;   if(low == high) return Max(A[low],0,0);   for(;i>=low;i--){      tmp+=A[i];      lret=Max(tmp,lret,0);   }    tmp=0;   for(;j<=high;j++){      tmp+=A[j];      rret=Max(tmp,rret,0);   }   return Max(lret+rret,fun(A,low,mid),fun(A,mid+1,high));}int main(){   int ret = fun(A,0,9);   printf("%d",ret);}

Output:187

 

 

问题2：

 问题描述：

1.求一个串中差值最小的两个数;

2,比如{2,6,3,8,11} 差值最小的显然是2和3,差值绝对值为|2-3|=1;

 

问题解决：

1.就以A={2,6,3,8,11} 为例，相邻位逐位相减得到B={a0-a1,a1-a2,a2-a3,a3-a4}={-4,3,-5,-3}

2.如果我们相求a2-a4=3-11，我们只需要用B中b2+b3=（a2-a3）+（a3-a4）= a2-a4=-5-3=-8;

 如果我们相求a0-a3=2-8，我们只需要用B中b0+b1+b2=（a0-a1）+（a1-a2）+（a2-a3）= -4+3-5=-6;

3.综上分析，求任意|a（i）- a（j）|的最小值，就是求数组B的和值绝对值最小的连续子序列（上一题是和值最大的连续子序列）与上一题相似;

4.代码与本文上一个算法类似，略;