专门做店铺转让的网站/怎么开一个网站平台

标题:java最大子序列求和，时间复杂度n,使用了分治，以及一种巧妙的方法

题目：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

一、初级版：
Java最大子序列求和

二、升级版
方法一：首先假设整形数组中最大值>0，故，只要一个for循环遍历，每次sum+=nums[i];若sum<0则继续遍历，若大于0，则比较sun与max，直到循环结束。
其次，若整形数组中最大值小于，只要用for循环找出最大值即可。

public int maxSubArray(int[] nums) {int sum=0;int max=nums[0];for(int i=0;i<nums.length;i++){if(nums[i]>max){max=nums[i];}}if(max<0){return max;}max=0;for(int i=0;i<nums.length;i++){sum+=nums[i];if(sum<0){sum=0;}else if(sum>max){max=sum;}}return max;}

方法二：使用分治，【起始也离不开递归】
1）首先可以分析得出，最大值子序列和可能在中间值的左侧【包括中间值】，右侧，或者中间地段【从中间值的左边包括左边第一个值开始找到最大子序列和+从中间值右侧包括右侧第一个值开始找到的最大子序列和】三个部分，接下来子需要递归就可以实现了，
2）三部分的第一、二部分，使用递归即可，第三部分，使用for循环得到包括左侧或右侧的第一个值开始的最大值【此处必须要for循环遍历到结尾与上面的方法一略微不同，，eg：-1,-20,100 || 1,5,-26】，

public int maxSubArray02(int[] nums) {return this.hhh(nums,0,nums.length-1);}public int hhh(int[] nums,int start,int end){if(start==end){return nums[start];}else{int mid=(start+end)/2;int maxLeft=hhh(nums,start,mid);int maxRight=hhh(nums,mid+1,end);int maxFirst=maxLeft>maxRight? maxLeft:maxRight;int sum1=nums[mid];int max1=nums[mid];for(int i=mid-1;i>=start;i--){sum1+=nums[i];if(max1<sum1){max1=sum1;}}int sum2=nums[mid+1];int max2=nums[mid+1];for(int i=mid+2;i<=end;i++){sum2+=nums[i];if(max2<sum2){max2=sum2;}}int maxSecond=max1+max2;return maxFirst>maxSecond? maxFirst:maxSecond;}}

方法如下：

/*** 真正的方法三、 n*/public int maxSubArray(int[] nums) {int sum=0;int max=nums[0];for(int i=0;i<nums.length;i++){if(nums[i]>max){max=nums[i];}}if(max<0){return max;}max=0;for(int i=0;i<nums.length;i++){sum+=nums[i];if(sum<0){sum=0;}else if(sum>max){max=sum;}}return max;}/*** 真正的方法四、  n  分治方法* 对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0,n−1][0, n - 1][0,n−1]，* 还可以用于解决任意的子区间 [l,r][l, r][l,r] 的问题。* 如果我们把 [0,n−1][0, n - 1][0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，* 即建成一颗真正的树之后，我们就可以在 O(log⁡n)O(\log n)O(logn) 的时间内求到任意区间内的答案，* 我们甚至可以修改序列中的值，做一些简单的维护，* 之后仍然可以在 O(log⁡n)O(\log n)O(logn) 的时间内求到任意区间内的答案，* 对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/*/public int maxSubArray02(int[] nums) {return this.hhh(nums,0,nums.length-1);}public int hhh(int[] nums,int start,int end){if(start==end){return nums[start];}else{int mid=(start+end)/2;int maxLeft=hhh(nums,start,mid);int maxRight=hhh(nums,mid+1,end);int maxFirst=maxLeft>maxRight? maxLeft:maxRight;int sum1=nums[mid];int max1=nums[mid];for(int i=mid-1;i>=start;i--){sum1+=nums[i];if(max1<sum1){max1=sum1;}}int sum2=nums[mid+1];int max2=nums[mid+1];for(int i=mid+2;i<=end;i++){sum2+=nums[i];if(max2<sum2){max2=sum2;}}int maxSecond=max1+max2;return maxFirst>maxSecond? maxFirst:maxSecond;}}