1.最大子序问题:在其使用动态规范和分而治之的策越:
package maxsequence; //模拟最大和子序列的;动态规划和分而治之思想 public class MaxSubSum { public static int begin=0,end=0; static void MaxSubSum4(int a[]) { //动态规划:负的子序列不能作为最大子序列的前缀码: int maxSum=0,thissum=0; //thisSum 计算每一次加入时候结果值,保证其中范围 int j,begintemp=0; int negativecount=0; for(j=0;j<a.length;j++) { thissum+=a[j]; if(a[j]<0) negativecount+=1; if(maxSum<thissum) { maxSum=thissum; end=j;//记录最后停止位置 begin=begintemp; } else if(thissum<0) { thissum=0; begintemp=j+1;//为每一次寻找最大值留出口; } } if(negativecount<a.length) { System.out.println("最大子序列之和:"+maxSum+"["+begin+','+end+"]"); System.out.println("test "+begintemp); } else { System.out.println("输入值全部是负数最大子序列规定是0"); } } private static int max3(int a,int b,int c) { int d=a>b?a:b; int e=d>c?d:c; int g=((a>b)?a:b)>c?((a>b)?a:b):c; return e; } private static int maxSumRec(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=maxSumRec(a,left,center); int MaxRightSum=maxSumRec(a,center+1,right); //规划一样,在左子序列中找到最大左子序列,为了计算出中间部分最大子序列 int maxLeftBorderSum=0,LeftBroderSum=0; for(int i=center;i>=left;i--) { LeftBroderSum+=a[i]; if(LeftBroderSum>maxLeftBorderSum) { maxLeftBorderSum=LeftBroderSum; begin=i; } } int maxReftBorderSum=0,ReftBroderSum=0; for(int i=center+1;i<=right;i++) { ReftBroderSum+=a[i]; if(ReftBroderSum>maxReftBorderSum) { maxReftBorderSum=ReftBroderSum; end=i; } } // return max3(MaxLeftSum,MaxRightSum,maxLeftBorderSum+maxReftBorderSum); } public static void MaxSubSum3(int []a) { System.out.println(maxSumRec(a,0,a.length-1)); System.out.println("["+begin+","+end+"]"); } public static void main(String[] args) { // TODO Auto-generated method stub int Data[]={-2,11,-20,13,-5,-1,35}; MaxSubSum4(Data); MaxSubSum3(Data);//通过递归,中间部分序列最大和=左序列最大和+右序列最大和 } }
最大子序列之和:42[3,6] test 3 42 [3,6]