最大子段和問題（分治法和動态規劃）

什麼是最大子段和，通俗點講：

        最大子段和就是給了一些數，然後你從中找了幾個連續的數，這組連續的數的和比任意一組連續的數的和都大，那麼你找的這幾個連續的數的和就是這些數的最大子段和。

通俗的聽不懂你就看這裡：

      給定由n個整數（可能為負整數）組成的序列

,

...

,求該序列形如

的子段和的最大值。當所有整數均為負整數時定義其最大子段和0。依此定義，所求的最優值為：

。例如，當(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為

= 20。

一、分治法

分治法思想：如果将所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n]，分别求出這兩段的最大子段和，則a[1:n]的最大子段和有三種情形：（不敲了。。。直接看圖）

#include<iostream>
using namespace std; 
int MaxSubSum(int *a,int left,int right){
	int sum = 0;
	if(left == right)
		sum = a[left] > 0 ? a[left] : 0;
	else{
		int center = (left + right)/2;
		int leftsum = MaxSubSum(a, left, center);
		int rightsum = MaxSubSum(a,center+1,right);

		int s1 = 0;
		int lefts = 0;
		for(int i =center;i>=left;i--){
			lefts +=a[i];
			if(lefts > s1)
				s1 = lefts;
		}	
		
		int s2 = 0;
		int rights = 0;
		for(int j = center +1;j<=right;j++){
			rights += a[j];
			if(rights> s2)
				s2 = rights;
		}

		sum = s1+s2;
		if(sum<leftsum)
			sum = leftsum;
		if(sum<rightsum)
			sum = rightsum;
	}
	return sum;
}

int MaxSum(int n,int *a){
	return MaxSubSum(a,0,n);
}

int main(){
	int a[] ={-2,11,-4,13,-5,-2};
	cout<<"最大子段和是:"<<MaxSum(5,a)<<endl;
	return 0;
}
           

二、動态規劃

動态規劃思想：設b[i]是以第i個數結尾的最大子段和，那麼從a[i]的角度來看，b[i]的值隻有兩種情況，如果 b[i-1]>0,那麼b[i]=b[i-1]+a[i]，否則b[i]=a[i]。（我覺得這個說法比書上的好了解）。

#include<iostream>
using namespace std;
int MaxSum(int n,int *a){
	int sum = 0, b = 0;
	for(int i =0;i<n;i++){
		if(b>0)
			b+=a[i];
		else
			b = a[i];
		if(b>sum)
			sum = b;
	}
	return sum;
}
int main(){
	int a[] = {-2,11,-4,13,-5,-2};
	cout<<"最大子段和:"<<MaxSum(5,a)<<endl;
	return 0;
}