1695. 删除子数组的最大得分(C++,滑动窗口)

简介: 1695. 删除子数组的最大得分(C++,滑动窗口)

给你一个正整数数组 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指针缩小窗口,直到窗口内所有元素都是唯一的。在此过程中,不断更新并比较最长子数组的和,最终返回最大的和作为结果。


相关文章
|
4月前
|
搜索推荐 编译器 C语言
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
105 4
|
4月前
|
C++
C++(十一)对象数组
本文介绍了C++中对象数组的使用方法及其注意事项。通过示例展示了如何定义和初始化对象数组,并解释了栈对象数组与堆对象数组在初始化时的区别。重点强调了构造器设计时应考虑无参构造器的重要性,以及在需要进一步初始化的情况下采用二段式初始化策略的应用场景。
|
5月前
|
算法 C++
c++学习笔记04 数组
这篇文章是C++学习笔记4,主题是数组。
51 4
|
5月前
|
C++ 索引
C++数组、vector求最大值最小值及其下标
C++数组、vector求最大值最小值及其下标
183 0
|
6月前
|
C++ 索引 运维
开发与运维数组问题之在C++中数组名和指针是等价如何解决
开发与运维数组问题之在C++中数组名和指针是等价如何解决
44 6
|
6月前
|
存储 安全 C++
开发与运维数组问题之声明一个数组如何解决
开发与运维数组问题之声明一个数组如何解决
48 6
|
6月前
|
存储 C++ 容器
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
71 5
|
6月前
|
C++
643. 子数组最大平均数 I(C++)
643. 子数组最大平均数 I(C++)
|
5月前
|
安全 编译器 C语言
C++入门-数组
C++入门-数组
|
6月前
|
算法 C++
2730. 找到最长的半重复子字符串(c++,滑动窗口)
2730. 找到最长的半重复子字符串(c++,滑动窗口)