问题描述：求-2,11,-4,13,-5,-2 的最大子序列和。
方法一：使用3层for循环嵌套，穷举式的尝试所有的可能，代码如下：
public class Demo1 {
public int maxSum(int a[]){
int maxSum=0;
for(int i=0;i<a.length;i++){
for(int j=i;j<a.length;j++){
int sum=0;
for(int k=i;k<=j;k++){
sum+=a[k];
if(sum>maxSum){
maxSum=sum;
}
}
}
}
return maxSum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Demo1 d=new Demo1();
int a[]={-2,11,-4,13,-5,-2};
System.out.println("最大子序列和为"+d.maxSum(a));
}
}
方法二：使用两个for循环嵌套：
public class Demo2 {
public int maxSum(int a[]){
int maxSum=0;
for(int i=0;i<a.length;i++){
int sum=0;
for(int j=i;j<a.length;j++){
sum+=a[j];
if(sum>maxSum){
maxSum=sum;
}
}
}
return maxSum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Demo2 d=new Demo2();
int a[]={-2,11,-4,13,-5,-2};
System.out.println("最大子序列和为"+d.maxSum(a));
}
}
方法三：使用分治策略，即把问题分成大致相等的子问题，然后递归对他们求解，然后得出最后的解。
public class Demo3 {
public int maxSum(int a[],int left,int right){
if(left==right){ //判断序列中元素是否只有一个
if(a[left]>0){
return a[left];
}
else
return 0;
}
int center=(left+right)/2; //求整个序列的中间值
int maxLeftSum=maxSum(a,left,center); //运用递归求左边的子序列的最大值
int maxRightSum=maxSum(a,center+1,right); // 运用递归求右边的子序列的最大值
int leftSum=0;
int maxLeft=0;
for(int i=center;i>=left;i--){ //求左边的最大子序列和
leftSum+=a[i];
if(leftSum>maxLeft){
maxLeft=leftSum;
}
}
int rightSum=0;
int maxRight=0;
for(int i=center+1;i<=right;i++){ //求右边的最大子序列和
rightSum+=a[i];
if(rightSum>maxRight){
maxRight=rightSum;
}
}
return max(maxLeftSum,maxRightSum,maxLeft+maxRight);
}
public int max(int a,int b,int c){ //求三个数中的最大值
int maxNum;
if(a>=b){
if(a>=c){
maxNum=a;
}
else
maxNum=c;
}
else
if(b>=c){
maxNum=b;
}
else
maxNum=c;
return maxNum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Demo3 d=new Demo3();
int a[]={-2,11,-4,13,-5,-2};
System.out.println("最大子序列和为："+d.maxSum(a,0,a.length-1));
}
}