Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Tags: Array, Divide and Conquer, Dynamic Programming
题意是求数组中子数组的最大和，这种最优问题一般第一时间想到的就是动态规划，我们可以这样想，当部分序列和大于零的话就一直加下一个元素即可，并和当前最大值进行比较，如果出现部分序列小于零的情况，那肯定就是从当前元素算起。其转移方程就是 dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);，由于我们不需要保留 dp 状态，故可以优化空间复杂度为 1，即 dp = nums[i] + (dp > 0 ? dp : 0);。
classSolution { publicintmaxSubArray(int[] nums) { intlen = nums.length, dp = nums[0], max = dp; for (inti = 1; i < len; ++i) { dp = nums[i] + (dp > 0 ? dp : 0); if (dp > max) max = dp; } returnmax; } }题目也给了我们另一种思路，就是分治，所谓分治就是把问题分割成更小的，最后再合并即可，我们把 nums 一分为二先，那么就有两种情况，一种最大序列包括中间的值，一种就是不包括，也就是在左边或者右边；当最大序列在中间的时候那我们就把它两侧的最大和算出即可；当在两侧的话就继续分治即可。
classSolution { publicintmaxSubArray(int[] nums) { returnhelper(nums, 0, nums.length - 1); } privateinthelper(int[] nums, intleft, intright) { if (left >= right) returnnums[left]; intmid = (left + right) >> 1; intleftAns = helper(nums, left, mid); intrightAns = helper(nums, mid + 1, right); intleftMax = nums[mid], rightMax = nums[mid + 1]; inttemp = 0; for (inti = mid; i >= left; --i) { temp += nums[i]; if (temp > leftMax) leftMax = temp; } temp = 0; for (inti = mid + 1; i <= right; ++i) { temp += nums[i]; if (temp > rightMax) rightMax = temp; } returnMath.max(Math.max(leftAns, rightAns), leftMax + rightMax); } }如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-java-leetcode
