企业官网建设流程全解析

题目

给你一个整数数组 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){intmax=Integer.MIN_VALUE;intminPrefixSum=Integer.MIN_VALUE;intsum=0;//前缀和数组int[]prefixSum=newint[nums.length+1];prefixSum[0]=0;minPrefixSum=prefixSum[0];for(inti=0;i<nums.length;i++){prefixSum[i+1]=prefixSum[i]+nums[i];//保存之前前缀和的最小值minPrefixSum=Math.min(minPrefixSum,prefixSum[i]);//当前前缀和与最小前缀和的差值sum=prefixSum[i+1]-minPrefixSum;max=Math.max(max,sum);}returnmax;}

注意不能是minPrefixSum = Math.min(minPrefixSum, prefixSum[i+1]);，minPrefixSum 应该保存当前位置之前的最小前缀和，否则如果是数组 [-1] 则会出现 (-1) - (-1) 的情况

方法三：动态规划

对于每个数字：需要考虑当前这个数字加入之前的连续子数组，还是重新开始，例如 nums=[-2,1,-3,4]到4的时候，前面的最大连续和为-2+1-3=-4如果加入-4+4=0但是直接从4开始：4更大。所以需要判断之前的贡献有没有价值。

• 每一个点处判断max(仅当前值，前面连续的最大值+当前值)
  

publicstaticintmaxSubArray(int[]nums){int[]dp=newint[nums.length];dp[0]=nums[0];intmax=dp[0];for(inti=1;i<nums.length;i++){dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);max=Math.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(left==right){returnnums[left];}intmid=(left+right)/2;intleftmax=divide(nums,left,mid);intrightmax=divide(nums,mid+1,right);intcrossmax=maxCross(nums,left,mid,right);returnMath.max(Math.max(leftmax,rightmax),crossmax);}publicstaticintmaxCross(int[]nums,intleft,intmid,intright){//左边最大后缀intleftmax=nums[mid];intsum=0;for(inti=mid;i>=left;i--){sum+=nums[i];leftmax=Math.max(leftmax,sum);}//右遍最大前缀intrightmax=nums[mid+1];sum=0;for(inti=mid+1;i<=right;i++){sum+=nums[i];rightmax=Math.max(rightmax,sum);}returnleftmax+rightmax;}publicstaticintmaxSubArray(int[]nums){returndivide(nums,0,nums.length-1);}