题目给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例 1输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2输入nums [1]输出1示例 3输入nums [5,4,-1,7,8]输出23提示1 nums.length 10^5-10^4 nums[i] 10^4进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。方法一暴力求解枚举所有子数组然后计算最大值。子数组数量O(n²)计算和O(n)总复杂度O(n³)方法二前缀和定义 preSum[i] 表示前 i 个元素的和那么一个区间 [i,j] 的和为 preSum[j]-preSum[i-1]publicstaticintmaxSubArray(int[]nums){intmaxInteger.MIN_VALUE;intminPrefixSumInteger.MIN_VALUE;intsum0;//前缀和数组int[]prefixSumnewint[nums.length1];prefixSum[0]0;minPrefixSumprefixSum[0];for(inti0;inums.length;i){prefixSum[i1]prefixSum[i]nums[i];//保存之前前缀和的最小值minPrefixSumMath.min(minPrefixSum,prefixSum[i]);//当前前缀和与最小前缀和的差值sumprefixSum[i1]-minPrefixSum;maxMath.max(max,sum);}returnmax;}注意不能是minPrefixSum Math.min(minPrefixSum, prefixSum[i1]);minPrefixSum 应该保存当前位置之前的最小前缀和否则如果是数组 [-1] 则会出现 (-1) - (-1) 的情况方法三动态规划对于每个数字需要考虑当前这个数字加入之前的连续子数组还是重新开始例如 nums[-2,1,-3,4]到4的时候前面的最大连续和为-21-3-4如果加入-440但是直接从4开始4更大。所以需要判断之前的贡献有没有价值。每一个点处判断max(仅当前值前面连续的最大值当前值)publicstaticintmaxSubArray(int[]nums){int[]dpnewint[nums.length];dp[0]nums[0];intmaxdp[0];for(inti1;inums.length;i){dp[i]Math.max(dp[i-1]nums[i],nums[i]);maxMath.max(max,dp[i]);}returnmax;}方法四分治法数组 [-2,1,-3,4,-1,2,1,-5,4] 中间切开分为 [-2,1,-3,4] 和 [-1,2,1,-5,4]那么最大子数组只有三种情况完全在左边完全在右边跨越中间也就是左边最大后缀 右边最大前缀。左边的最大后缀就从最后一个数字开始依次计算取最大值右边最大前缀从第一个数字开始以此计算取最大值最后依次递归合并publicstaticintdivide(int[]nums,intleft,intright){if(leftright){returnnums[left];}intmid(leftright)/2;intleftmaxdivide(nums,left,mid);intrightmaxdivide(nums,mid1,right);intcrossmaxmaxCross(nums,left,mid,right);returnMath.max(Math.max(leftmax,rightmax),crossmax);}publicstaticintmaxCross(int[]nums,intleft,intmid,intright){//左边最大后缀intleftmaxnums[mid];intsum0;for(intimid;ileft;i--){sumnums[i];leftmaxMath.max(leftmax,sum);}//右遍最大前缀intrightmaxnums[mid1];sum0;for(intimid1;iright;i){sumnums[i];rightmaxMath.max(rightmax,sum);}returnleftmaxrightmax;}publicstaticintmaxSubArray(int[]nums){returndivide(nums,0,nums.length-1);}