题目：给定一个长度为n的整数序列，求它的最大连续子序列和in:-2,1,3,4,-1,2,1,-5,4 out:4,-1,2,1,=6
一滑动区间(暴力解法)
先固定左边界，右边界滑动
然后左边界右移一位，再执行右边界滑动
public class 最大连续子序列和 { public static void main(String[] args) { // 滑动区间（暴力解法） int[] nums=new int[]{-2,1,-3,4,-1,2,1,-5,4};// if(nums==null||nums.length==0) System.out.println(0); int max=0; for(int begin=0;begin<nums.length;begin++){//左边界 int sum=0;//[begin,end]都为闭区间 for(int end=begin;end<nums.length;end++){//右边界 sum+=nums[end]; max=Math.max(sum, max); } } System.out.println(max); } }二、分治（归并）
将序列均匀分割为两个子序列 [begin,end]=[begin,mid)+[mid,end],mid=(begin+end)>>1 ->除以2的意思 假设问题解为S[i,j),那么解有3种情况 一、[i,j)->[begin,mid) ; 二、[i,j)->[mid,end) ; 三、[i,mid)+[mid,j);
public class 最大连续子序列和 { //给定一个长度为n的整数序列，求它的最大连续子序列和in:-2,1,3,4,-1,2,1,-5,4 out:4,-1,2,1,=6 public static void main(String[] args) { //分治 //将序列均匀分割为两个子序列 //[begin,end]=[begin,mid)+[mid,end],mid=(begin+end)>>1 ->除以2的意思 //假设问题解为S[i,j),那么解有3种情况 //一、[i,j)->[begin,mid) ; 二、[i,j)->[mid,end) ; 三、[i,j)->[i,mid)+[mid,j); int[] nums={-2,1,-3,4,-1,2,1,-5,4};// System.out.println(maxSum(nums,0,nums.length)); } public static int maxSum(int[] nums,int begin,int end){ if(end-begin<2) return nums[begin]; //第三种情况 int mid=(begin+end)>>1; int leftMax=Integer.MIN_VALUE; int leftSum=0; for(int i=mid-1;i>=begin;i--){//中间向左加 leftSum +=nums[i]; leftMax=Math.max(leftMax,leftSum); } int rightMax=Integer.MIN_VALUE; int rightSum=0; for(int i=mid;i<end;i++){//中间向右加 rightSum +=nums[i]; rightMax=Math.max(rightSum,rightMax); } int max=rightMax+leftMax;//第3种情况：mid向右加，mid向左加 //int leftSum=maxSum(nums,begin,mid); //int rightSum=maxSum(nums,mid,begin); return Math.max(max, Math.max( maxSum(nums,begin,mid), maxSum(nums,mid,begin))); } }
