LeetCode 53. Maximum Subarray

题目Given an integer arraynums, 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.几百年没做差点以为是prefix sum或者sliding window。也是看了答案才知道是dp以及并没有一次性写出来……当个复读机重复一下以前写的我觉得写挺好这道题的思路其实很简单题目要求找出数组中连续的几个数字之和的最大。由于数组是连续的因此我们以以nums[i]结尾的数组为基准来划分子问题把它表示为sum[i]那么sum[i]只有两种情况要么是nums[i]自己白手起家要么是在它前面的sum[i - 1]的基础之上锦上添花因此这个问题就变成了sum[i] max(sum[i - 1] nums[i], nums[i])。因为这题的dp状态转移比较简单只depends on前一个的状态所以其实可以不用存数组直接用变量表示。用数组class Solution { public int maxSubArray(int[] nums) { int[] dp new int[nums.length]; dp[0] nums[0]; int result dp[0]; for (int i 1; i nums.length; i) { dp[i] Math.max(nums[i], dp[i - 1] nums[i]); result Math.max(result, dp[i]); } return result; } }用变量以及根据gpt老师这是一个算法名字叫Kadanes Algorithmclass Solution { public int maxSubArray(int[] nums) { int currSum 0; // can use 0 as its calculated in the for loop int maxSum nums[0]; for (int i 0; i nums.length; i) { currSum Math.max(nums[i], currSum nums[i]); maxSum Math.max(maxSum, currSum); } return maxSum; } }番外为啥不是prefix sum或者sliding windowaccording to GPT老师为啥不用prefix sum我们需要找到最大子数组和而不是计算某个已知区间的和。如果直接枚举所有区间左端点有 \(O(n)\) 种选择。右端点有 \(O(n)\) 种选择。使用前缀和可以让每次区间求和降到 \(O(1)\)。总时间复杂度仍然是 \(O(n^2)\)。不过Prefix Sum 也可以进一步优化到 \(O(n)\)所以并不是说这题不能用前缀和而是前缀和不是最直观的解题思路。为啥不用sliding windowSliding Window 通常适用于这样的场景窗口满足某个条件时尝试扩大窗口窗口不满足条件时尝试缩小窗口缩小窗口能够让我们有规律地恢复条件。例如数组全是正数时寻找“和不超过 \(K\) 的最长连续子数组”就可以用滑动窗口。因为右端点右移会让窗口和增大左端点右移会让窗口和减小。但 Maximum Subarray 的数组可以包含任意正数和负数。滑动窗口最重要的前提是窗口条件随左右端点移动具有足够的单调性或可维护性。 这道题的最大子数组和没有提供常规滑动窗口所需的性质。以下来自久远的2019:这道题可是两年前在水算法作业的时候做过的题翻了以前的博客发现以前不会做巧了现在也不会做。题目一看就想到了动态规划可是却没想出来到底怎么划分子问题看了以前的记录才想到解法然后瞬间就写出了代码并发现之前那个代码绝壁不是我写的以前的我怎么这么水啊。这道题的思路其实很简单题目要求找出数组中连续的几个数字之和的最大。由于数组是连续的因此我们以以nums[i]结尾的数组为基准来划分子问题把它表示为sum[i]那么sum[i]只有两种情况要么是nums[i]自己白手起家要么是在它前面的sum[i - 1]的基础之上锦上添花因此这个问题就变成了sum[i] max(sum[i - 1] nums[i], nums[i])。我自己写的代码如下时间复杂度O(n)运行时间12ms只打败了5%看了下以前抄的代码发现可以用max()来简化那些if们class Solution { public: int maxSubArray(vectorint nums) { int max nums[0]; int sum nums[0]; for (int i 1; i nums.size(); i) { if (sum nums[i] nums[i]) { sum nums[i]; } else { sum nums[i]; } if (sum max) { max sum; } } return max; } };使用max()以后代码看起来清晰整洁的版本class Solution { public: int maxSubArray(vectorint nums) { int currentSum nums[0], totalSum nums[0]; for(int i1; inums.size(); i) { //Current max sum is either the current element OR current element Previous Maximum subarray) currentSum max(nums[i], currentSumnums[i]); //If the current maximum array sum is greater than the global total. Update it totalSum max(totalSum, currentSum); } return totalSum; } };2020.10.1 Java依旧差点没想到dp表达式卑微。Runtime: 1 ms, faster than 68.70% of Java online submissions for Maximum Subarray.Memory Usage: 38.9 MB, less than 96.46% of Java online submissions for Maximum Subarray.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; i nums.length; i) { dp[i] Math.max(dp[i - 1] nums[i], nums[i]); if (dp[i] max) { max dp[i]; } } return max; } }还有另一种和这个思路很相似的解法设置一个currentSum和一个totalSum分别存储截至当前nums[i]的sum和全局的最大值代码如下int maxSubArray(vectorint nums) { int currentSum 0, totalSum INT_MIN; for(int i0; inums.size(); i) { //Sum till this point Current Sum till this point this element currentSum currentSum nums[i]; //If the current maximum array sum is greater than the global total. Update it totalSum max(totalSum, currentSum); //If you get current as less thn 0 then its no point in carrying forward. Make it 0 currentSum max(0,currentSum); } return totalSum; }感觉这种解法的第一句和第三句的合体就是DP解法的第一句假设当前遇到的nums[i]会使totalSum减小那么currentSum将保存当前的结果并在nums[i 1]的时候加入nums[i 1]与totalSum比较。理解的感觉不是特别到位强行解释了一番因为这个方法让我自己想我是想不到的只能在了解方法以后自己在纸上模拟一遍以上两个代码均来自于https://leetcode.com/problems/maximum-subarray/discuss/118509/C-Kadanes-Algorithm总结的很好然后看到题目底下还有个follow up说是可以用分治算法来解决看了下以前的记录发现是没有的想了一会儿还是想不到分治的解法。看了discussion里大佬的解法大概就是把原始的数组分成左右两半分别递归最后要找的max的可能性有三种要么完全是在已经分成的左右两边的一边中要么就可能是横跨左右两边并包含中间的元素。然而就算是知道了这种解法但依旧不会写代码orz 真实的递归无能了。基本上抄着大佬的代码打出了如下代码并加了点自己的注释运行时间8ms击败了35%的C submissionclass Solution { public: int maxSubArray(vectorint nums) { return maxSub(nums, 0, nums.size() - 1); } int maxSub(vectorint nums, int l, int r) { if (l r) { return INT_MIN; } // recursion for left and right part int m (l r) / 2; int lmax maxSub(nums, l, m - 1); int rmax maxSub(nums, m 1, r); // find out the max closest to the middle int ml 0, mr 0; int sum 0; for (int i m - 1; i l; i--) { sum nums[i]; ml max(ml, sum); } sum 0; for (int i m 1; i r; i) { sum nums[i]; mr max(mr, sum); } // return either the max in the left/right, or combines both side and the middle return max(max(lmax, rmax), ml mr nums[m]); } };这份代码的参考来源https://leetcode.com/problems/maximum-subarray/discuss/20452/C%2B%2B-DP-and-Divide-and-Conquer