当前位置: 首页> 文旅> 文化 > 【动态规划】力扣918. 环形子数组的最大和

【动态规划】力扣918. 环形子数组的最大和

时间:2025/7/10 20:12:47来源:https://blog.csdn.net/sjsjs11/article/details/140918156 浏览次数:0次

给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], …, nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

在这里插入图片描述

动态规划

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> leftMax(n);int pre = nums[0], res = nums[0], leftSum = nums[0] ;leftMax[0] = nums[0];for(int i = 1; i < n; i++){pre = max(nums[i], pre + nums[i]);res = max(res, pre);leftSum += nums[i];leftMax[i] = max(leftMax[i-1], leftSum);}int rightSum = 0;for(int i = n - 1; i > 0 ; i--){rightSum += nums[i];res = max(res, rightSum + leftMax[i-1]);}return res;}
};

时间复杂度:O(n),其中 n 是 nums 的长度。求解第一种情况的时间复杂度为 O(n),求解 leftMax 数组和枚举后缀的时间复杂度为 O(n),因此总的时间复杂度为 O(n)。

空间复杂度:O(n),其中 n 是 nums 的长度。过程中我们使用 leftMax 来存放最大前缀和。

用动态规划的思路来讲,是要列出可能的情况。在这道题中一种情况是不跨越尾部,也就是正常的子段,另外一种是跨越尾部。针对特殊的跨越尾部的情况,使用leftMax来记录第 i 个元素之前的最大子段和,然后从右到左遍历数组,最后比较两种情况的最大值即可。

取反

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();int sum = nums[0];int preMax = nums[0], resMax = nums[0];int preMin = nums[0], resMin = nums[0];for(int i = 1; i < n; i++){preMax = max(nums[i], preMax + nums[i]);resMax = max(resMax, preMax);preMin = min(nums[i], preMin + nums[i]);resMin = min(resMin, preMin);sum += nums[i];}if(resMax < 0){return resMax;}else{return max(resMax, sum - resMin);}}
};

时间复杂度:O(n),其中 n 是 nums 的长度。
空间复杂度:O(1)。过程中只是用到了常数个变量。

这是一个更加巧妙的思路,并且有更低的空间复杂度。他的思想是所有数组元素之和减去中间的一段最小子段和,剩下的部分就是最大的经过头尾的子段和,再与正常子段和比较即可。要注意的是,当resMax < 0 的时候,sum - resMin返回的是一个空数组,这时候只要返回resMax。

关键字:【动态规划】力扣918. 环形子数组的最大和

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: