个人网站排名欣赏/软件推广的渠道是哪里找的

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例:

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法思路：

没有很好的方法，直接暴力遍历所有情况；

class Solution {public int maxSubArray(int[] nums) {int max=Integer.MIN_VALUE;//特殊状态if(nums==null||nums.length==0)return max;//前缀和//prefixSum[1]=nums[0];//prefixSum[2]=nums[0]+num[1];//...//prefixSum[index]=nums[0]+...nums[index-1];int[] prefixSum=new int[nums.length+1];prefixSum[0]=0;for(int index=0;index<nums.length;index++){prefixSum[index+1]=prefixSum[index]+nums[index];}//连续数组长度1~nums.lengthfor(int len=1;len<=nums.length;len++){//连续数组起始位置for(int index=0;index<=nums.length-len;index++){max=Math.max(max,prefixSum[index+len]-prefixSum[index]);}}return max;}
}

提交效果：

时间和空间复杂度分析：

时间复杂度：O(n^2)

空间复杂度：O(n)

某大师表示这解法太垃圾了，帮我改了改：

class Solution {public int maxSubArray(int[] nums) {int max=Integer.MIN_VALUE;if(nums==null||nums.length==0)return max;//最优前缀和数组int[] prefixSum=new int[nums.length];//第0个数的前缀和即是第0个数prefixSum[0]=nums[0];for(int index=1;index<nums.length;index++){//若第index-1个数的前缀对第index个数的前缀和有增益效果,则第index个数的前缀和添加增益效果;if(prefixSum[index-1]>0){prefixSum[index]=prefixSum[index-1]+nums[index];}else{//若第index-1个数的前缀对第index个数的前缀和没增益效果,则直接舍去第index-1个数前缀和的累赘prefixSum[index]=nums[index];}}//思考，现在的优先前缀和是啥？//第index个数的前缀和是必然包含第index个数的一个和数;兄弟，别怀疑,这就是一句废话！！//此时反向思考，本题目需要求整数组nums中连续数列的最大和数，这里转达一个意思即我们得在一组数中找到一个最大值，但是这组数是啥？这组数是以第0个数为结尾的连续数列最大值，以第1个数为结尾的连续数列最大值，以第2个数为结尾的连续数列最大值... 以第index个数为结尾的连续数列最大值...以第(nums.length-1)个数为结尾的连续数列最大值;你细品，慢慢品，不就是上面的最优前缀和吗？  for(int index=0;index<nums.length;index++){max=Math.max(max,prefixSum[index]);}return max;}
}

提交效果：

大师不愧为大师，稍微修改修改，就提升了这么多，真滴牛啊！！

时间空间复杂度分析：

时间复杂度: O(n)

空间复杂度: O(n)

复盘：

某大师的基本思路是什么？ DP

熟悉DP的人都知道DP通常具有三个特性，重叠子问题，状态转移方程，最优子结构;

首先本题需要理顺的问题便是这里的最优子结构在如何构造问题？

数组nums的连续数组最大和数 = {以第0个数为尾数的前缀子数组最大和数，以第1个数为尾数的前缀子数组最大和数…以第n-1个数为尾数的前缀子数组最大和数} 此集合最大值；

此时问题转变为求第index个数为尾数前缀子数组？

设dp(i)表示:以第i个数为尾数的前缀子数组最大和数，若dp(i-1)<0,则此时的上个前缀和有点像个累赘，只会导致当前的dp(i)更小，若dp(i)>0,则可添加上个前缀和；

状态转移方程：dp(i)=Math.max(dp(i-1)+nums[i], nums[i])

重新整理：

class Solution {public int maxSubArray(int[] nums) {int max=Integer.MIN_VALUE;if(nums==null||nums.length==0)return max;//子结构最大值int[] subMax=new int[nums.length];subMax[0]=nums[0];max=subMax[0];//子结构生成时即比较最大值for(int index=1;index<nums.length;index++){subMax[index]=Math.max(subMax[index-1]+nums[index],nums[index]);max=Math.max(max,subMax[index]);}return max;}
}