java-子序列最大值

java-求一序列中子序列的最大值

###三次循环:T(n)=O(n^3)

public static int maxSubseqSum1(int[] a, int n) {
		int i, j, k;
		int max = 0, sum = 0;
		for (i = 0; i < n; i++) {// i是子列左端位置
			for (j = i; j < n; j++) {// j是子列右端位置
				sum = 0; // 从a[i]至a[j]的和
				for (k = i; k <= j; k++) {
					sum += a[k];
				}
				if (sum > max) {
					max = sum;
				}
			} // j循环结束

		} // i循环结束
		return max;
	}

###两次循环:T(n)=O(n^2)

public static int maxSubseqSum2(int[] a, int n) {
		int i, j, k;
		int max = 0, sum = 0;
		for (i = 0; i < n; i++) {// i是子列左端位置
			sum=0;
			for (j = i; j < n; j++) {// j是子列右端位置
				sum+=a[j];
				if(sum>max) {
					max=sum;
				}
			} // j循环结束
		} // i循环结束
		return max;
	}

###分而治之:T(n)=O(nlogn)
下图引用

分析：分治法主要思想就是把问题划分成若干个子问题，每个子问题所要寻求的答案是一致的，只需要求出每个子问题的解，所求问题就可以更好的求解
eg:该例可以把初始序列看做只有三个元素的序列即4 -3 5
根据二分法需要知道的是left:左端点 、right:右端点 、mid:中间值，其中值得注意的是
若 mid=(right+left)/2 则递归子任务为(left,mid)、(mid+1,right)
若 mid=(left+right+1)/2 则递归子任务为(left,mid-1)、(mid,right)
继续分析4 -3 5对于该序列left=0、right=length-1=2、mid=(right+left)/2 =1 则左边的递归子任务划分为(0,1),右边的递归子任务为(2),对于递归任务来说终止条件为left==right(找到自身),首先就可以求出(0,1)递归中最大和为4，(2)中最大和为5，这只是解决问题的一步，另一步是需要求出以mid为界跨越两边的最大和，最终比较三值之间即leftmax、rightmax、crossmax之间的最大值即为解

public static int maxCross(int[] a, int left,int right,int mid) {
		
	
		int leftmax=0,rightmax=0;//中间值
		
		int leftsum=a[mid];//左边最大之和
		int rightsum=0;//有边最大之和
		for(int i=mid;i>=0;i--) {//跨越两边，左边是一个一个寻找
			leftmax+=a[i];
			if(leftmax>leftsum) {
				leftsum=leftmax;
			}
		}
		for(int j=mid+1;j<=right;j++) {//跨越两边，右边是一个一个寻找,注意right取到=:传过来的right值已经是符合条件的！！！
			rightmax+=a[j];
			if(rightmax>rightsum) {
				rightsum=rightmax;
			}
		}
		
		return leftsum+rightsum;
		
	}
	
	public static int max(int a,int b) {
		return a>b?a:b;
	}
	
	public static int findMax(int[] a,int left,int right) {
	if(left==right) return a[left];//递归终止条件，找到自己
	   
	    int mid=(left+right)/2;
	    int leftmax=findMax(a,left,mid);
	    int rightmax=findMax(a,mid+1,right);
	    int cross=maxCross(a,left,right,mid);
	    return max(max(leftmax,rightmax),cross);
	}

###在线处理：T(n=O(n)

public static int maxSubseqSum4(int[] a, int n) {
		int i;
		int  thissum=0,maxsum=0; //thissum:及时判断当前子列，如果出现负值不能为后面创造价值则抛弃
		for (i = 0; i < n; i++) {// i是子列左端位置
			thissum+=a[i];
			if(thissum>maxsum) {
				maxsum=thissum;
			} //end if
			else if(thissum<0){
				thissum=0;         //及时更0,计算新的子列和
			}
		} // i循环结束
		return maxsum;
	}

总结：以下是上述用到的算法或者相关概念需要注意的地方
1.递归一般不要使用，当规模较大时，有可能会溢栈，要小心使用。其次，递归要有终止条件!!
2.数组：数组下标从0开始，最大下标为length-1
3.二分法mid取值情况不同，递归子任务的传值不同!!!