动态规划-最大子段和问题

思路: 将给定的序列分为长度相等的两段,a[1,n/2],a[n/2+1,n]；

1：最大子段和在a[1,n/2]里面；

2：最大子段和在a[n/2+1,n]里面；

3: 最大子段和在a[i,j]里面,其中i位于(1,n/2),j位于(n/2+1,n)；

1,2情况直接递归求解,对于3可分别求出1，2中的最大值，然后相加。再与1，2中的最大值比较。得出最终的最大子段和。

代码:

/*
  @求解最大子段和 
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int maxSum(int a[],int left,int right){
	int sum  = 0;
	if(left==right){
		sum = a[left]>0?a[left]:0;
	}
	else{
		int mid = (left+right)/2;
		int leftsum = maxSum(a,left,mid);       //左部分最大值 
		int rightsum = maxSum(a,mid+1,right);   //右部分最大值 
		int  max1 = 0,lefts = 0;
	    for(int i = mid;i>=left;i--){       //最大值分布在左右部分
		     lefts+=a[i]; 
	    	 if(lefts>max1){
	    	 	max1 = lefts;
			 }
	    	 else{
	    	 	;
			 } 
		}
		int  max2 = 0,rights = 0;
	    for(int j = mid+1;j<=right;j++){
	    	rights+=a[j];
	    	if(rights>max2){
	    	 	max2 = rights;
			}
	    	else{
	    	 	;
			} 
	    }
		    sum = max1+max2;
		if(sum<leftsum){
			sum = leftsum;
		}
		if(sum<rightsum){
			sum = rightsum;
		}
	}
    return sum;
}

int main(int argc, char** argv) {
    int a[6] = {-5,13,-6,18,-4,-3};
	cout<<maxSum(a,1,6)<<endl;	
	return 0;
}