【题目描述】

给出一个长度位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(n³)。事实上，可将算法中的最后一个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(n²)的计算时间。

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

如果将所给的序列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(a_i~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;
}