leetcode 1695. 删除子数组的最大得分 中等

给你一个正整数数组 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;
}