算法设计与分析第二章作业

        分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

基本思想：

(1) 将求解的较大规模的问题分割成k个更小规模的子问题。

(2) 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

(3) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

最大字段和的问题：

问题： 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20。最大字段和是动态规划中的一种。

最大字段和的分治算法：

（1）思想：

可以从数组中间分开，结果要么在左边或右边，要么就在中间。结果在左边和右边的情况好办，那在中间的情况该如何分析呢？因为子段是连续的，所以结果只能从中心向两边扩，采用枚举法，左右走到尽头，结果相加就得到中间的最大解。所以该题采用分治算法的难度就可以解决了。

拆分子数组分别求得的最大子段和为sum1,sum2。时间复杂度为2T(N/2),从中心点向两边找最大的和，找到跨越的最大子段和的时间复杂度为O(n), 所以总体的时间复杂度为：T(n)=2T(n/2)+O(n) = O(nlogn)。

（2）算法的伪代码实现：

（3）代码实现：

#include 
using namespace std;

int b[100010]; // 归并算法需要另外再开一个数组 
void Merge(int* a, int left, int mid, int right){ // 在最小数组中进行逐一比对放入b数组 
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right){
		if(a[i] < a[j]){
			b[k++] = a[i++];
		}
		else{
			b[k++] = a[j++];
		}
	}
	while (i <= mid)
		b[k++] = a[i++];
	while (j  <= right)
		b[k++] = a[j++];
	for (int i = 0; i < k; i++){
		a[left+i] = b[i]; // 注意此时的数组不是从0开始排序，而是从left开始排序 
	}
}
void MergeSort(int* a, int left, int right){
	if(left >= right) return; // 大于等于还是等于都是可以的 
	int mid = (left + right) / 2;
	MergeSort(a, left, mid); // 不断递归，切分为非递减的最小数组，然后拼接 
	MergeSort(a, mid+1, right);
	Merge(a, left, mid, right);
}
int main(){
	int n;
	int a[100010];
	cin >> n;
	for(int i=0; i> a[i];
	}
	MergeSort(a, 0, n-1); //0表示的是最左边的索引，n-1表示最右边的索引 
	for (int i=0; i