剑指 Offer 42. 连续子数组的最大和（动态规划+贪心算法+分治算法） |
您所在的位置：网站首页 › 剑指offer和leetcode区别 › 剑指 Offer 42. 连续子数组的最大和（动态规划+贪心算法+分治算法） |
剑指 Offer 42. 连续子数组的最大和（动态规划+贪心算法+分治算法）
|
题目描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof 1:动态规划O(n)时间复杂度 && O(n)空间复杂度 class Solution { public int maxSubArray(int[] nums) { //动态规划 int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = dp[0]; for(int i = 1; imax) max = cur; former=cur; } return max; } } class Solution { public int maxSubArray(int[] nums) { //动态规划 int dp_0 = nums[0]; int max = dp_0; for(int i = 1; i res) res = sum; if(sum left - 1; i--) { curSum += nums[i]; leftSubsum = std::max(leftSubsum, curSum); } // 贪心法求右边的最大值 int rightSubsum = INT_MIN; curSum = 0; for (int i = mid + 1; i 1，采用分治法求解最大连续子序列时，取其中间位置mid=(n-1)/2，此时序列被分成2部分，左边为[0,mid],右边为[mid+1,n-1] 该子序列只可能出现3个地方。 (1）该子序列完全落在左半部即a[0…mid]中。采用递归求出其最大连续子序列和maxLeftSum。
(2)该子序列完全落在右半部即a[mid+1…n-1]中。采用递归求出其最大连续子序列和maxRightSum.
注意，下面这个例子是我看的B站的视频讲解，该题当数组全为负数时，返回0，与我们的题意不太一致，思路一样，实现代码稍作修改即可。 视频：chapt3-4-组合-最大连续子序列和 对于数组[-2,11,-4,13,-5,2],先找到中间位置，分成[-2,11,-4]和[13,-5,-2], 现在，先分析[-2,11,-4]，继续拆分，直到每个子序列长度都为1， 先分成了[-2,11]和[-4],再把[-2,11]分成[-2], [11]， 那么[-2]这个子序列，我们记其最大子序列和为0，因为它小于0嘛，[11]这个子序列，我们记其最大子序列和为11, 那我们就分别得到了[-2,11]的maxLeftSum,maxRightSum,还需要计算[-2,11]的maxLeftBorderSum+maxRightBorderSum 从下图可以看出，[-2,11]的maxLeftBorderSum+maxRightBorderSum值为11，那么对于序列[-2,11]，max(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)=11
版本1： class Solution { public int maxSubArray(int[] nums) { return maxSubArray(nums,0,nums.length-1); } int maxSubArray(int[]arr,int left,int right) { int maxLeftSum=0,maxRightSum=0; int maxLeftBorderSum=0,maxRightBorderSum=0,LeftBorderSum=0,RightBorderSum=0; int mid=(left+right)/2; if(left==right)//当切分到只有一个元素 { return arr[left]; } maxLeftSum=maxSubArray(arr,left,mid); maxRightSum=maxSubArray(arr,mid+1,right); int croSum = crossSum(arr, left, right, mid); return Math.max(Math.max( maxLeftSum,maxRightSum), croSum); } int crossSum(int []nums, int left, int right, int mid) { // 分解到一个值时返回该值 if (left == right) { return nums[left]; } // 贪心法求左边的最大值 int leftSubsum =Integer.MIN_VALUE; int curSum = 0; for (int i = mid; i > left - 1; i--) { curSum += nums[i]; leftSubsum =Math.max(leftSubsum, curSum); } // 贪心法求右边的最大值 int rightSubsum = Integer.MIN_VALUE; curSum = 0; for (int i = mid + 1; i =left;i--) { LeftBorderSum+=arr[i]; if(LeftBorderSum>maxLeftBorderSum) { maxLeftBorderSum=LeftBorderSum; } } maxRightBorderSum=Integer.MIN_VALUE; RightBorderSum=0; for(int j=mid+1;jmaxRightBorderSum) { maxRightBorderSum=RightBorderSum; } } return Math.max(maxLeftSum,Math.max(maxRightSum, maxLeftBorderSum+maxRightBorderSum)); } }
浅谈分治算法的时间复杂度分析 cn * Log2n + cn = cn(1+Log2n) 即 Ѳ(nLog2n).
贪心+分治+动态规划法_面试题42. 连续子数组的最大和 剑指 Offer 42. 连续子数组的最大和（动态规划） 从暴力破解到动态规划 视频：chapt3-4-组合-最大连续子序列和 浅谈分治算法的时间复杂度分析 |
(3)该子序列跨越序列a的中部而占据左右两部分。
所以，对于序列[-2,11,-4,13,-5,2],max(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)=max（11,20,13）=20
在每个层上的时间复杂度为: 第在一层上是cn(c为比较一次时所用的时间), 在第二层上时数组被分成了两部分, 每部分为 n/2, 则在第二层上时间为 c * n/2 + c* n/2 = cn, 同样在第三层上, 被分成了四部分, 时间为cn/4 + cn/4 + cn/4 + cn/4 = cn. 层高一共是按刚才说的是Log2n层,每一层上都是cn, 所以共消耗时间 cn * Log2n; 则总时间:
【本文地址】
今日新闻 |
推荐新闻 |