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


相关文章
|
3月前
|
存储 C++
C++指针数组
C++指针数组
33 1
|
26天前
|
C++ 索引 运维
开发与运维数组问题之在C++中数组名和指针是等价如何解决
开发与运维数组问题之在C++中数组名和指针是等价如何解决
18 6
|
27天前
|
存储 安全 C++
开发与运维数组问题之声明一个数组如何解决
开发与运维数组问题之声明一个数组如何解决
32 6
|
26天前
|
存储 C++ 容器
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
37 5
|
4天前
|
安全 编译器 C语言
|
1月前
|
C++
643. 子数组最大平均数 I(C++)
643. 子数组最大平均数 I(C++)
|
1月前
|
算法 C++
2730. 找到最长的半重复子字符串(c++,滑动窗口)
2730. 找到最长的半重复子字符串(c++,滑动窗口)
|
1月前
|
C++
567. 字符串的排列(c++)滑动窗口
567. 字符串的排列(c++)滑动窗口
|
2月前
|
存储 安全 算法
C++的内置数组和STL array、STL vector
C++的内置数组和STL array、STL vector
|
2月前
|
存储 算法 安全
C++一分钟之-数组与指针基础
【6月更文挑战第19天】在C++中,数组和指针是核心概念,数组是连续内存存储相同类型的数据,而指针是存储内存地址的变量。数组名等同于指向其首元素的常量指针。常见问题包括数组越界、尝试改变固定大小数组、不正确的指针算术以及忘记释放动态内存。使用动态分配和智能指针可避免这些问题。示例代码展示了安全访问和管理内存的方法,强调了实践的重要性。
36 3