每日一题 - 剑指 Offer 42. 连续子数组的最大和

每日一题 - 剑指 Offer 42. 连续子数组的最大和

题目信息

时间： 2019-06-30

题目链接：Leetcode

tag： 动态规划

难易程度：简单

题目描述：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例:

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

注意

1. 1 <= arr.length <= 10^5 2. -100 <= arr[i] <= 100

解题思路

本题难点

常见解法时间复杂度空间复杂度暴力搜索O(N^2)O(1)分治思想O(NlogN)O(logN)动态规划O(N)O(1)

具体思路

动态规划

状态定义：设动态规划列表 dp ，dp[i]]代表以元素 nums[i] 为结尾的连续子数组最大和。转移方程： 若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。 当dp[i-1]>0时，执行dp[i]=dp[i-1] + nums[i]当dp[i-1]<0时，执行dp[i]=nums[i] 初始状态：dp[0] = nums[0]

代码

class Solution { public int maxSubArray(int[] nums) { if(nums == null || nums.length == 0){ return 0; } int sum = nums[0]; int former = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0 int cur= nums[0];//用于记录dp[i]的值 for(int num: nums){ if(former <= 0){ cur = num; } if(former > 0){ cur = former + num; }//这两句话等同于 cur = Math.max(former,0) + num; former = cur; sum = Math.max(sum,cur); } return sum; } }

复杂度分析：

时间复杂度 O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。空间复杂度 O(1) ： 使用常数大小的额外空间。

其他优秀解答

解题思路

分治法，我们把数组nums以中间位置（mid)分为左（left)右(right)两部分. 那么有， left = nums[0]…nums[m - 1] 和 right = nums[m + 1]…nums[n-1]

最大子序列和的位置有以下三种情况：

考虑中间元素nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和

代码

class MaximumSubarrayDivideConquer { public int maxSubArrayDividConquer(int[] nums) { if (nums == null || nums.length == 0) return 0; return helper(nums, 0, nums.length - 1); } private int helper(int[] nums, int l, int r) { if (l > r) return Integer.MIN_VALUE; int mid = (l + r) >>> 1; int left = helper(nums, l, mid - 1); int right = helper(nums, mid + 1, r); int leftMaxSum = 0; int sum = 0; // left surfix maxSum start from index mid - 1 to l for (int i = mid - 1; i >= l; i--) { sum += nums[i]; leftMaxSum = Math.max(leftMaxSum, sum); } int rightMaxSum = 0; sum = 0; // right prefix maxSum start from index mid + 1 to r for (int i = mid + 1; i <= r; i++) { sum += nums[i]; rightMaxSum = Math.max(sum, rightMaxSum); } // max(left, right, crossSum) return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right)); } }