给你一个正整数数组 nums
,请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b
是数组 a
的一个连续子序列,即如果它等于 a[l],a[l+1],...,a[r]
,那么它就是 a
的一个子数组。
示例 1:
输入:nums = [4,2,4,5,6] 输出:17 解释:最优子数组是 [2,4,5,6]
示例 2:
输入:nums = [5,2,1,2,5,2,1,2,5] 输出:8 解释:最优子数组是 [5,2,1] 或 [1,2,5]
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
分析:用一个 index 数组,记录 nums 数组中每个数出现的下标,初始化为 -1。遍历 nums 数组,最初时取得的最优子数组区间的左端点 l = 0,右端点为循环下标 i。如果 nums[i] 为 -1,说明还没有出现过,则将当前的子数组和 sum 加上 nums[i],并修改 index[nums[i]] = i。如果nums[i] 不为 -1,则将 l 到 nums[i] 的所有值从 sum 中减去, 并更新 index 数组中对应值的下标为 -1,表示去掉这些值,最后把 l 更新为上一次 nums[i] 出现位置的后一位。遍历完数组,取 sum 的最大值即可。
int maximumUniqueSubarray(int* nums, int numsSize) {int index[100010]={0};for(int i=0;i<100010;++i)index[i]=-1;int ans=0,sum=0,l=0;for(int i=0;i<numsSize;++i){if(index[nums[i]]!=-1) {int r=index[nums[i]];for(int j=l;j<=r;++j)sum-=nums[j],index[nums[j]]=-1;l=r+1;}sum+=nums[i],index[nums[i]]=i,ans=fmax(sum,ans);}ans=fmax(sum,ans);return ans;
}