最大子段和问题（分治法和动态规划）

什么是最大子段和，通俗点讲：

        最大子段和就是给了一些数，然后你从中找了几个连续的数，这组连续的数的和比任意一组连续的数的和都大，那么你找的这几个连续的数的和就是这些数的最大子段和。

通俗的听不懂你就看这里：

      给定由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; }