一个app下载网站,北京建设教育协会网站首页,保定网站制作设计哪个公司好,西安网站建设那家强做环形数组最大和之前先做一下数组最大和 53.数组最大和
题目链接#xff1a;LeetCode53.数组最大和 本体使用动态规划或者贪心
动态规划
class Solution {
public:int maxSubArray(vectorint nums) {vectorintdp(nums.size(),0);dp[0]nums[0];int an… 做环形数组最大和之前先做一下数组最大和 53.数组最大和
题目链接LeetCode53.数组最大和 本体使用动态规划或者贪心
动态规划
class Solution {
public:int maxSubArray(vectorint nums) {vectorintdp(nums.size(),0);dp[0]nums[0];int ansnums[0];for(int i1;inums.size();i) {int num dp[i-1]nums[i];if(numnums[i]) dp[i]num;else dp[i]nums[i];ans ansdp[i]?ans:dp[i];}return ans;}
};贪心
class Solution {
public:int maxSubArray(vectorint nums) {int sumnums[0];int ans nums[0];for(int i1;inums.size();i){sumnums[i];if(sumnums[i]) sumnums[i];ans anssum?ans:sum;}return ans;}
};918.环形数组的最大和
题目链接LeetCode918环形数组的最大和
动态规划
求解普通数组的最大子数组和是求解环形数组的最大子数组和问题的子集。设数组长度为n下标从0开始在环形数组中答案可能包括以下两种情况
构成最大子数组和的子数组为nums[i:j]包括nums[i]到nums[j-1]共j-i个元素其中0ijn构成最大子数组和的子数组为nums[0:i]和nums[j:n]其中0ijn 第二种情况中答案可以分为两部分nums[0:i]为数组的某一前缀,nums[j:n]为数组的某一后缀。求解时可以枚举j,固定sum(nums[j:n])的值然后找到右端点坐标范围在[0,j-1]的最大前缀和将它们相加更新答案。
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorintleftmax(n,0);//记录数组的前缀最大子数组和下标从0开始leftmax[0]nums[0];int sumnums[0];//用来记录普通数组的子数组的和int resnums[0];//普通数组的最大子数组和int leftsumnums[0];for(int i1;in;i){sumnums[i];if(sumnums[i]) sumnums[i];res ressum?res:sum;leftsumnums[i];leftmax[i]leftmax[i-1]leftsum?leftmax[i-1]:leftsum;}if(res0) return res;//数组中的元素都是负数//固定后缀int rightsum0;for(int in-1;i0;--i){rightsumnums[i];res max(res,leftmax[i-1]rightsum);}return res;}
};取反
对于第二种情况可以找到普通数组最小的子数组nums[i-j]。令maxRes是普通数组的最大子数组和minRes是普通数组的最小子数组和可以将maxRes与sum(nums[0-n])-minRes取最大值作为答案。
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int sumnums[0];//求解数组的和int summaxnums[0],maxresnums[0];//最大子数组和int summinnums[0],minresnums[0];//最小子数组和for(int i1;inums.size();i){summax max(summaxnums[i],nums[i]);maxres max(maxres,summax);summin min(summinnums[i],nums[i]);minres min(minres,summin);sumnums[i];}//coutmaxres minres sum;if(maxres0) return maxres;return max(maxres,sum-minres);}
};单调队列
可以将数组延长一倍即对于in的元素令nums[i]nums[i-n] 对于第二种情况nums[0:i]和nums[j:n]可以组成连续的一段因此问题转换为一个在长度为2n的数组上寻找长度不超过n的最大子数组和(每个位置的元素只能使用一遍)。令si为前i项的前缀和找到最大的si-sj其中i-nji用单调队列维护该集合
遍历到i时单调队列头部元素下标小于i-n则出队。该过程一直进行直至队列为空或者队头下标大于等于i-n取队头元素作为j计算si-sj更新答案若队列尾部元素k满足sksi则出队该过程一直进行直至队列为空或者条件不满足因为kik更容易被步骤1剔除并且作为被减项sk比si更大更不具有优势。
class Solution {
public:typedef pairint,int pa;//位置到前缀和的映射int maxSubarraySumCircular(vectorint nums) {int sumnums[0],resnums[0];int n nums.size();dequepa qu;qu.push_back(pa(0,sum));for(int i1;i2*n;i){sumnums[i%n];while(!qu.empty()qu.front().firsti-n) {qu.pop_front();}res max(res,sum-qu.front().second);while(!qu.empty()qu.back().secondsum){qu.pop_back();}qu.push_back(pa(i,sum));}return res;}
};
