本文主要是介绍leetcode 918.环形子数组的最大和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:DP
其实和昨天做的哪个重复数组差不多,按顺序来说先做这个题目其实更好。
这里需要分两种情况:第一个,就是数组不越界的时候,这个时候最大子数组和就是leetcode 53题的题解。
如果说越界了,我们还需要注意一点,就是如果你想用链表的方式再加上一个数组,这是不可取的,这里的题目要求直接给你禁止这种耍小聪明的方法了。(同余下标的两个数不能同时取)
所以我们只能想别的办法这里有一点,就是和最小子数组和相联系的一点,就是当我们求出来最小子数组和的时候,剩下的元素不就是最大子数组和了吗?(sum-最小子数组和,sum为总的数组和)你可能会说,啊,这个不是连续的吗?这就是一个技巧问题了,我们可以认为是连续的,因为题目中不就说了吗,是循环的,所以我们越界的时候其实本质上也是连续的。
这样就能解决问题了,最大值就是max(maxs,sum-mins)。
但是还有一种特殊情况,就是当sum==mins也就是最小子数组和就是这个数组本身的和,这里就直接认为是maxs了,为什么?你想,如果是这样的话,那么是不是就不存在最小子数组和了吗?只剩下了最大子数组和了?sum-mins会是0,但是maxs不一定>0,所以我们需要特殊关照一下。
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();int max_dp=0;int min_dp=0;int maxs=INT_MIN;int mins=INT_MAX;int sum=0;for(int i=0;i<n;i++){max_dp=max(max_dp,0)+nums[i];min_dp=min(min_dp,0)+nums[i];maxs=max(maxs,max_dp);mins=min(min_dp,mins);sum+=nums[i];}return sum==mins?maxs:max(sum-mins,maxs);}
};
这篇关于leetcode 918.环形子数组的最大和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!