给你一个正整数数组 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
int ans=0,sum=0; // ans表示最终要返回的最长子数组的和,sum表示当前窗口内元素的和 vector<int> visit(10001,0); // visit数组用于记录每个元素在当前窗口内出现的次数,数组大小设为10001,应根据实际情况调整 // 使用双指针技巧,l表示窗口左边界,r表示窗口右边界 for (int l=0, r=0; r < nums.size(); ++r) { printf("*"); // 打印 '*',用于调试或者显示运行过程中的一些信息 visit[nums[r]]++; // 将nums[r]元素加入窗口,计数加一 sum += nums[r]; // 更新当前窗口的元素和 // 如果窗口内nums[r]元素的个数大于1,说明窗口内有重复元素 while (visit[nums[r]] > 1) { visit[nums[l]]--; // 移动左边界l,减少窗口内nums[l]元素的计数 sum -= nums[l]; // 更新窗口的元素和,减去nums[l]的值 l++; // 左边界右移,缩小窗口 } ans = max(ans, sum); // 更新最长子数组的和 cout << "ans=" << ans << endl; // 打印当前最长子数组的和,用于调试或显示 } return ans; // 返回最长子数组的和
这段代码使用了滑动窗口(双指针)的方法来动态维护一个不包含重复元素的子数组,并实时更新子数组的和。主要思想是,用r指针扩展窗口并添加新元素,同时更新窗口的和;当窗口内出现重复元素时,移动l指针缩小窗口,直到窗口内所有元素都是唯一的。在此过程中,不断更新并比较最长子数组的和,最终返回最大的和作为结果。