转载

求连续子数组的最大和问题

前言

这几天一直在读Weiss的数据结构书( Data Structures and Algorithm Analysis in C:Second Edition )，其中第二章是关于简单的算法分析（引入大O记号等工具），以“求连续子数组的最大和问题”为例，进行了一些说明和阐释。 最大子数组和问题 （原书翻译为“最大的子序列和问题”）实际上我去年夏天暑假在家刷学院OJ的时候就见过，后来秋天开算法课，在上机时也有碰到。在网上看到这还是一道经典的面试题目，在此结合Weiss的书做一点总结性讨论。

问题描述

一个整数数组中的元素有正有负，在该数组中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2}，最大连续子数组的和为5+2-1+2=8。问题输入就是一个数组，输出该数组的“连续子数组的最大和”。

思路分析

这个问题我所见的有四种不同时间复杂度的算法。暴力模拟显然是最慢的，而应用动态规划思想，可以得到一个O(N)级别的线性时间算法，再它的基础上稍微变形，可以得到一个更简洁的形式。Talk is cheap, let's show codes.

代码

Solution 1: 暴力模拟，三层循环，O(n^3)级别

  int MaxSubsequenceSum1(const int A[],int N)   {       int ThisSum=0 ,MaxSum=0,i,j,k;       for(i=0;i<N;i++)         for(j=i;j<N;j++)         {               ThisSum=0;               for(k=i;k<=j;k++)                 ThisSum+=A[k];                             if(ThisSum>MaxSum)                   MaxSum=ThisSum;           }           return MaxSum;   }

Solution 2:在Solution1基础上撤出一个for循环，O(N^2)级别

 int MaxSubsequenceSum2(const int A[],int N)   {       int ThisSum=0,MaxSum=0,i,j,k;       for(i=0;i<N;i++)     {           ThisSum=0;           for(j=i;j<N;j++)         {               ThisSum+=A[j];               if(ThisSum>MaxSum)                   MaxSum=ThisSum;           }       }       return MaxSum;   }

Solution 3: 分治法，分支界限的处理思路。

因为最大子序列和可能在三处出现，整个出现在数组左半部，或者整个出现在右半部，又或者跨越中间，占据左右两半部分。递归将左右子数组再分别分成两个数组，直到子数组中只含有一个元素，退出每层递归前，返回上面三种情况中的最大值。

根据这样的分析，写出代码：

  static int MaxSubSum(const int A[],int Left,int Right)   {       int MaxLeftSum,MaxRightSum;              //左、右部分最大连续子序列值     int MaxLeftBorderSum,MaxRightBorderSum;  //从中间分别到左右两侧的最大连续子序列值     int LeftBorderSum,RightBorderSum;       int Center,i;       if(Left == Right)Base Case           if(A[Left]>0)               return A[Left];           else               return 0;           Center=(Left+Right)/2;            MaxLeftSum=MaxSubSum(A,Left,Center);  //递归调用         MaxRightSum=MaxSubSum(A,Center+1,Right);            MaxLeftBorderSum=0;  LeftBorderSum=0;           for(i=Center;i>=Left;i--)           {               LeftBorderSum+=A[i];               if(LeftBorderSum>MaxLeftBorderSum)                   MaxLeftBorderSum=LeftBorderSum;           }            MaxRightBorderSum=0;  RightBorderSum=0;           for(i=Center+1;i<=Right;i++)           {               RightBorderSum+=A[i];               if(RightBorderSum>MaxRightBorderSum)                   MaxRightBorderSum=RightBorderSum;           }           //比较各种情况，求出最大值         int max1=MaxLeftSum>MaxRightSum?MaxLeftSum:MaxRightSum;           int max2=MaxLeftBorderSum+MaxRightBorderSum;           return max1>max2?max1:max2;   }

另外一份写的更清晰的代码：

 /* 求三个数中的最大值 */ int Max3(int a,int b,int c) {     int Max = a;     if(b > Max)         Max = b;     if(c > Max)         Max = c;     return Max; }   int MaxSubSum2(int *arr,int left,int right) {     int MaxLeftSum,MaxRightSum;    //左右边的最大和     int MaxLeftBorderSum,MaxRightBorderSum;    //含中间边界的左右部分最大和     int LeftBorderSum,RightBorderSum;    //含中间边界的左右部分当前和     int i,center;      //递归到最后的基本情况     if(left == right)         if(arr[left]>0)             return arr[left];         else             return 0;      //求含中间边界的左右部分的最大值     center = (left + right)/2;     MaxLeftBorderSum = 0;     LeftBorderSum = 0;     for(i=center;i>=left;i--)     {         LeftBorderSum += arr[i];         if(LeftBorderSum > MaxLeftBorderSum)             MaxLeftBorderSum = LeftBorderSum;     }     MaxRightBorderSum = 0;     RightBorderSum = 0;     for(i=center+1;i<=right;i++)     {         RightBorderSum += arr[i];         if(RightBorderSum > MaxRightBorderSum)             MaxRightBorderSum = RightBorderSum;     }      //递归求左右部分最大值     MaxLeftSum = MaxSubSum2(arr,left,center);     MaxRightSum = MaxSubSum2(arr,center+1,right);      //返回三者中的最大值     return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum); }  /* 将分支策略实现的算法封装起来 */ int MaxSubSum2_1(int *arr,int len) {     return MaxSubSum2(arr,0,len-1); }

以上代码时间复杂度为O(NlogN)

Solution 4: 动态规划(DP)

不难得出，针对这个问题，递推公式是DP[i] = max{DP[i-1] + A[i],A[i]}；既然转移方程出来了，意味着写一层循环就可以解决这个问题。

将这个转移方程变为形象的if-else判断，代码（来源于Weiss的书）为：

 int MaxSubSum(int arr[],int len)   {       int i;       int MaxSum = 0;       int ThisSum= 0;       for(i=0;i<len;i++)       {           ThisSum+= arr[i];           if(ThisSum > MaxSum)               MaxSum = ThisSum;           /*如果累加和出现小于0的情况，              则和最大的子序列肯定不可能包含前面的元素，              这时将累加和置0，从下个元素重新开始累加  */         else if(ThisSum< 0)               ThisSum= 0;       }       return MaxSum;   }

最后贴一份我去年暑假过学校OJ题时AC的代码。

 #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; int MaxsumUlt(int * arr, int size) {     int maxSum = 0xf0000000;     int sum = 0;     for(int i = 0; i < size; ++i)     {         if(sum < 0)         {             sum = arr[i];         }         else         {             sum += arr[i];         }         if(sum > maxSum)         {             maxSum = sum;         }     }     return maxSum; }  int main(){     int n;     while(cin>>n){     int a[n];     for(int i = 0;i<n;i++)         cin>>a[i];     printf("%d /n",MaxsumUlt(a,n));     }  }