LC1695. 删除子数组的最大分数

题目描述

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

题目解析

题目在说什么

题目给了你一个正整数数组，比如 [4,2,4,5,6]。你可以从中删掉一个连续的子数组（也就是原数组中连续的一段），但这个子数组里不能有重复的数字。删掉之后，你的得分就是子数组里所有数字的和。你要找出能得到的最大得分。

比如示例1，删掉 [2,4,5,6] 得分是 2+4+5+6=17，这是最大的。注意不能删 [4,2,4] 因为里面有重复的4，不符合条件。

简单说：在数组中找一个最长的、没有重复数字的连续子数组，因为数字都是正数，越长和越大，但必须保证不重复。

思路是怎么来的

想象你在一排水果摊前，每个摊上卖一种水果，价格不同（数字代表价格）。你想买连续几个摊的水果，但每种水果只能买一次（不能重复），而且你想花最多的钱。你该怎么选？

一个直观的想法是：你从左到右逛，每看到一个摊，如果这种水果之前没买过，就把它加进购物车，记下当前总价。如果遇到之前买过的水果，比如前面已经买过苹果，这里又出现苹果，那你就得从购物车里扔掉最早买的那个苹果，甚至可能还要扔掉苹果之前买的其他水果，直到购物车里没有重复为止。这样你就能保证购物车里始终是不重复的连续一段。

这个“逛摊”的过程，就是滑动窗口。窗口的左端是你购物车里最早买的水果位置，右端是你当前看的位置。窗口里永远没有重复水果。你每逛一个新摊，就更新一下最大总价。最后记录下来的最大总价就是答案。

代码逐步拆解

我们来看参考代码，一行一行讲清楚。

int sums = 0;          // 当前窗口里所有数字的和
int largest = 0;       // 记录到目前为止最大的和
HashSet<Integer> hash = new HashSet<Integer>();  // 用来判断数字是否重复
int start = 0;         // 窗口的左边界（从数组下标0开始）

• sums 就像购物车里的总价，一开始是0。
• largest 用来记“到目前为止最好的成绩”，一开始也是0。
• hash 是一个集合，里面存了窗口里出现过的数字，用来快速检查新数字是否重复。
• start 是窗口左端的位置，初始在数组开头。

for( int end = 0 ; end < nums.length ; end++ ){

• end 是窗口的右端，从0开始往右移动，每次看一个新数字。

    while(hash.contains(nums[end])){
        sums -= nums[start];
        hash.remove(nums[start]);
        start++;
    }

• 如果新数字 nums[end] 已经在 hash 里了，说明窗口里有重复。这时候就要收缩窗口左边，把左边元素一个一个移出去，直到重复的那个元素也被移出去。
• 每移出一个元素 nums[start]，sums 要减去它的值，hash 里也要删掉它，然后 start 右移一位。
• 这个 while 循环可能执行多次，直到窗口里没有重复为止。

    hash.add(nums[end]);
    sums += nums[end];
    largest = Math.max(largest, sums);

• 现在窗口里没有重复了，可以放心地把新数字 nums[end] 加进窗口。
• 更新 sums（加上新数字），然后更新 largest（看看当前和是不是比之前记录的最大和还大，是的话就更新）。

return largest;