删除子数组的最大得分

给你一个正整数数组 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 <= 105
1 <= nums[i] <= 104
通过次数2,099提交次数5,758

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-erasure-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

前缀和介绍：

设数列为：
A=[1，2，3，4，5，6]
那么他的前缀和是
S=[1，3，6，10，15，21]

如果需要计算A[2]到A[5]的和只需要计算A[5]-A[1]=20
即当i<=j时，A[i]到A[j]的和为:

sum=A[j]-A[i-1]

用一个指针记录上次字符开始的位置，如果中间有一个元素i与当前的元素重复了，就从开始位置开始查找，直至找到与当前元素重复的元素i，把i位置之前的元素全部删除。

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int[] preSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {             //计算前缀和
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int max = 0, sum = 0, start = 0;

        for (int i = 0; i < nums.length; i++) {             //从前往后向集合中加入子数组中的元素
            if (!set.contains(nums[i])) {                   //如果遇到重复的元素
                set.add(nums[i]);
                sum = preSum[i+1] - preSum[start];          
                max = Math.max(sum, max);                   //计算当前的最大和
            } else {                                        //如果遇到重复的元素
                while (nums[i] != nums[start]) {            //从加入集合的第一个元素开始查找，如果该元素不是重复元素，说明还有这部分元素是重复数字之前的元素，从列表中删除
                    set.remove(nums[start]);
                    start++;
                }
                sum -= preSum[start];                       //计算删除重复元素之后的最大和（重复元素之前的那部分和也不能要了）
                start++;
            }
        }
        return max;
    }
}

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0, sum = 0, start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
                sum += nums[i];
                max = Math.max(sum, max);
            } else {
                while (nums[i] != nums[start]) {
                    sum -= nums[start];
                    set.remove(nums[start]);
                    start++;
                }
                start++;
            }
        }
        return max;
    }
}

参考文献

作者：nian-zi-zai-zi
链接：https://leetcode-cn.com/problems/maximum-erasure-value/solution/hua-dong-chuang-kou-shuang-bai-by-nian-z-8gfv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信