企业自助建站网,playyo wordpress,聚美优品网站建设策划书,网站平台推广语录作者 | 码农的荒岛求生来源 | 码农的荒岛求生今天给大家带来一道极其经典的题目#xff0c;叫做最大和子数组#xff0c;给定一个数组#xff0c;找到其中的一个连续子数组#xff0c;其和最大。示例#xff1a;输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 子数组… 作者 | 码农的荒岛求生来源 | 码农的荒岛求生今天给大家带来一道极其经典的题目叫做最大和子数组给定一个数组找到其中的一个连续子数组其和最大。示例输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 子数组[4,-1,2,1]的和为6其它任何连续的子数组和不超过6。想一想该怎样解决这个问题。如果你一时想不到解法可以从暴利解法开始。暴力求解这种解法最简单我们把所有子数组找出来然后依次计算其和找出一个最大的出来比如给定数组[1,2,3]那么我们能找出子数组[1][2][3][1,2][2,3][1,2,3]很显然这里和最大的子数组为[1,2,3]其值为6。int sum(vectorintnums, int b,int e){int res 0;for (; b e; b) {res nums[b];}return res;
}
int maxSubArray(vectorint nums) {int size nums.size();int res 0x80000000;for (int i 0; i size; i) {for (int j i; j size; j) {res max(res, sum(nums, i, j));}}return res;
}这种解法最简单该算法的时间复杂度为O(n^3)其中找出所有子数组的时间复杂度为O(n^2)计算每个子数组的和的时间复杂度为O(n)因此其时间复杂度为O(n^3)。让我们再来看一下这个过程这里的问题在于计算每个子数组的和时有很多重复计算比如我们知道了子数组[1,2]的和后再计算数组[1,2,3]的值时完全可以利用子数组[1,2]的计算结果而无需从头到尾再算一遍也就是说我们可以利用上一步的计算结果这本身就是动态规划的思想。基于该思想我们可以对上述代码简单改造一下int maxSubArray(vectorint nums) {int size nums.size();int res 0x80000000;for (int i 0; i size; i) {int sumer nums[i];res max(res, sumer);for (int j i 1; j size; j) {sumer nums[j];res max(res, sumer);}}return res;
}看到了吧代码不但更简洁而且运行速度更快该算法的时间复杂度为O(n^2)比第一种解法高了很多。还有没有进一步提高的空间呢答案是肯定的。分而治之我们可以把整个数组一分为二然后子数组也一分为二不断划分下去就像这样然后呢然后问题才真正开始有趣起来注意当我们划分到最下层的时候也就是不可再划分时会得到两个数组元素比如对于数组[1,2]会划分出[1]与[2]此时[1]与[2]不可再划分那么对于子问题[1,2]其最大子数组的和为max(12, 1,2)也就是说要么是左半部分的元素值、要么是右半部分的元素值、要么是两个元素的和就这样我们得到了最后两层的答案假设对于数组[1,2,3,4]一次划分后得到了[1,2]与[3,4]用上面的方法我们可以分别知道这两个问题的最大子数组和我们怎样利用上述的答案来解决更大的问题也就是[1,2,3,4]呢很显然对于[1,2,3,4]来说最大子数组的和要么来自左半部分、要么来自右半部分、要么来自中间部分——也就是包含2和3其中左半部分和右半部分的答案我们有了那么中间部分的最大和该是多少呢其实这个问题很简单我们从中间开始往两边不断累加然后记下这个过程的最大值比如对于[1,-2,3,-4,5]我们从中间的3开始先往左边累加和是:{1(-2)3, (-2)3, 3}也就是{2,1,3}因此我们以中间数字为结尾的最大子数组和为3另一边也是同样的道理只不过这次是以中间数字为起点向右累加然后这三种情况中取一个最大值即可这样我们就基于子问题解决了更大的问题此后的道理一样最终我们得到了整个问题的解。根据上面的分析就可以写代码了int getMaxSum(vectorint nums, int b, int e) {if (b e) return nums[b];if (b e - 1) return max(nums[b], max(nums[e], nums[b]nums[e]));int m (b e) / 2;int maxleft nums[m];int maxright nums[m];int sum nums[m];for (int i m 1; i e; i) {sum nums[i];maxright max(maxright, sum);}sum nums[m];for (int i m - 1; i b; i--) {sum nums[i];maxleft max(maxleft, sum);}return max(getMaxSum(nums, b, m - 1), max(getMaxSum(nums, m 1, e), maxleftmaxright-nums[m]));
}
int maxSubArray(vectorint nums) {return getMaxSum(nums, 0, nums.size()-1);
}上述这段代码的时间复杂度为O(NlogN)比第二种方法又提高了很多。动态规划实际上这个问题还有另一种更妙的解决方法我们令dp(i)表示以元素A[i]为结尾的最大子数组的和那么根据这一定义则有这是很显然的注意dp(i)的定义是以元素A[i]为结尾的最大子数组的和因此dp(i)的值要么就是A[i]连接上之前的一个子数组那么不链接任何数组那么最终的结果一定是以某个元素为结尾的子数组因此我们从所有的dp(i)中取一个最大的就好了依赖子问题解决当前问题的解就是所谓的动态规划。有了这些分析代码非常简单int maxSubArray(vectorint nums) {int size nums.size();vectorint dp(size, 0);int res dp[0] nums[0];for (int i 1; i size; i) {dp[i] max(dp[i - 1] nums[i], nums[i]);res max(res, dp[i]);}return res;
}这段代码简单到让人难以置信只有8行代码你甚至可能会怀疑这段代码的正确性但它的确是没有任何问题的而且这段代码的时间复杂度只有O(N)这段代码既简单运行速度又快这大概就是算法的魅力吧。往期推荐从 40% 跌至 4%“糊”了的 Firefox 还能重回巅峰吗Gartner 发布 2022 年汽车行业五大技术趋势别再用 Redis List 实现消息队列了Stream 专为队列而生漫画什么是“低代码”开发平台点分享点收藏点点赞点在看
