【题目描述】

给出一个长度位n的序列a,选出其中连续且非空的一段使得这段和最大

【输入描述】

第一行是一个整数，表示序列的长度n。

第二行有n个整数，第i个整数表示序列的第i个数字ai

【输出描述】

输出一行一个整数表示答案。

【样例输入】

7  2 -4 3 -1 2 -4 3

【样例输出】

4

【题目分析】

1. 比较经典的题目，可以用暴力求解、分治法求解、动态规划求解

   
   
   

   ---

   
   
   

   
   
   

【最大子段和——暴力求解】

算法描述：

int MaxSum(int n,int *a, int& besti,int& bestj) {  	int sum=0;  	for(int i=1; i<=n; i++)  		for(int j=1; j<=n; j++) {  			int thissum=0;  			for(int k=i; k<=j; k++)  				thissum+=a[k];  			if(thissum>sum) {  				sum=thissum;  				besti=i;  				bestj=j;  			}  		}  	return sum;  }

从上面这个算法的三个for循环可以看出，它所需的计算时间是O(n3)。事实上，可将算法中的最后一个for循环省去掉，避免重复计算，从而使算法得以改进。

int MaxSum(int n,int *a, int& besti,int& bestj) {  	int sum=0;  	for(int i=1; i<=n; i++)  		int thissum=0;  		for(int j=i;j<=n;j++){  			thissum+=a[j];  			if(thissum>sum){  				sum=thissum;  				besti=i;  				bestj=j;  			}  		}	  	return sum;  }

过程图解：

当i=1时

当i=2时

依次类推。。

改进后的算法显然只需要O(n2)的计算时间。

【最大子段和——分治算法】

如果将所给的序列a[1 : n]分为长度相等的两端a[1 : n/2]和a[n/2+1 : n], 分别求出这两段的最大子段和，则a[1 : n]的最大字段和有三种情形。

（1）a[1 : n] 的最大子段和 与 a[1 : n/2 ]的最大子段和相同；

（2）a[1 : n]的最大子段和 与 a[ n/2 +1 : n] 的最大子段和相同；

（3）a[1 : n]的最大子段和 为sum(ai~j)。且1<=i<=n/2;  n/2+1 <= j <=n;

其中，（1）和（2）这两种情形可以通过递归求得。对于情形3，容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，可以在a[1 : n/2]中计算出 左段最大值s1和右端最大值s2。则s1+s2即为出现情形3时的最优值。

int MaxSum(int* a, int beg, int end){      if (beg == end){          return a[beg] > 0? a[beg] :0;      }      int mid = (beg + end) / 2;      int max_left = MaxSum(a, beg, mid);      int max_right = MaxSum(a, mid + 1 ,end);      int s1 = 0, s2 = 0, m_left = 0, m_right = 0;      for(int i = mid; i <= beg; i --){          s1 += a[i];          if(s1 > m_left)              m_left = s1;      }      for(int i = mid+1; i <= end; i ++){          s2 += a[i];          if(s2 > m_right)              m_right = s2;      }      int max_sum = max_left;      if(max_right > max_sum)          max_sum = max_right;      if(m_right + m_left > max_sum)          max_sum = m_left + m_right;      return max_sum;  }

时间复杂度O(nlogn)

【最大子段和——动态规划】

给定n个整数（可能为负数）组成的序列a1,a2,…,an。求该序列形如下式的子段和的最大值：

当所有整数均为负整数时定义其最大子段和为0。 依次定义，所求的最优值为：

例如： (a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) 该序列的最大子段和为：

通过对分治算法的分析可知，若记：

（b[j]表示从1到j的最大子段和）

则所求的最大子段和为：

（上面的公式是由分治思想得出的）

由b[j]的定义可知： 当时：

否则：

a[j]是某个具体值，b[j]是某一段的和（如果你学过前缀和的话，这个地方就很好理解了）

输入数据：

7  2 -4 3 -1 2 -4 3

(是考虑到分治算法的第三种情况，可以参考下面的图解)：

由此可得b[j]的动态规划递归式：

递推表达式：

                                                    dp[i] = max{dp[i-1] + A[i], A[i]}

int max = 0;  for(int i = 1; i <= n; i ++){     if(dp[i-1] > 0){          dp[i] = dp[i-1] + A[i];     }else{          dp[i] = A[i];     }     if(dp[i]> max){          max = dp[i];     }  }

递归解法：

int MaxSum(int n, int *a) {  	int sum=0,b=0;  	for(int i=1;i<=n;i++){  		if(b>0)   			b+=a[i];  		else  			b=a[i];  		if(b>sum)  			sum=b;  	}  	return sum;  }