分治法求01背包问题c语言

#include <iostream> using namespace std; int MaxSum(int a[],int left,int right)//分治法 { int sum=0; if (left==right) { if(a[left]>0) sum=a[left]; else sum=0; } else { int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=MaxSum(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; } void main(){ int n,a[100],m ,maxsum; cout<<"请输入整数序列的元素个数："<<endl; cin>>n; cout<<"请输入各元素的值："<<endl; for(m=1;m<=n;m++) cin>>a[m]; maxsum=MaxSum(a,1,n); cout<<"最大子段和是："<<maxsum<<endl; system("pause"); }