tb的区间问题时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述t b tbtb给了f c fcfc一个长度为n nn的数组A AA,f c fcfc对A AA进行k kk次如下操作删除数组第一个元素或者删除数组最后一个元素。求最后得到的数组和的最大值。输入描述第一行输入两个正整数n , k ( 1 ≤ k ≤ n ≤ 5 × 10 3 ) n,k(1≤k≤n≤5×10^3)n,k(1≤k≤n≤5×103)分别表示数组长度以及操作次数。第二行输入n nn个整数表示A AA数组第i ii个数为a i ( 0 ≤ a i ≤ 10 9 ) a_i(0≤a_i≤10^9)ai​(0≤ai​≤109)。输出描述一个非负整数表示最后得到数组和的最大值。示例1输入5 4 8 13 7 8 6输出13解题思路本题核心是通过问题转化将删边操作简化为固定长度子数组求和再用滑动窗口高效求解。1. 问题等价转化每次只能从数组头部或尾部删除一个元素执行 k 次删除后剩余元素一定是原数组中一段连续的中间子数组长度固定为l e n n − k len n - klenn−k。因此原问题等价于在数组中找到一个长度为 len 的连续子数组使得其元素和最大。2. 算法固定长度滑动窗口对于固定长度的最大子数组和问题滑动窗口法可以达到线性时间复杂度先计算第一个窗口前 len 个元素的元素和作为初始最大值。窗口向右逐位滑动每次加上右端新进入窗口的元素减去左端移出窗口的元素得到新的窗口和。每次滑动后更新全局最大和。当 len 0即 k n时所有元素被删除答案为 0。时间复杂度为O ( n ) O(n)O(n)空间复杂度为O ( n ) O(n)O(n)存储数组完全适配题目数据规模。总结核心逻辑将首尾删元素的操作转化为求固定长度的连续子数组最大和通过滑动窗口一次遍历即可得到结果避免了暴力枚举的平方级开销。代码简要说明代码采用滑动窗口思路实现但存在一处初始值逻辑疏漏仅在窗口滑动时更新最大值res未将第一个窗口的和纳入最大值统计。当最优窗口恰好位于数组最左端时会得到错误结果样例因最优窗口不在左端而输出正确。具体代码逻辑变量定义nums维护当前窗口的元素和res记录最大和初始为0存在疏漏。窗口初始化遍历数组前n-k个元素累加得到第一个窗口的和。窗口滑动从第n-k个元素开始每次计算新窗口的和更新最大值与当前窗口和。修正建议初始化完第一个窗口后将res赋值为第一个窗口的和再执行滑动更新即可覆盖所有情况。输入优化关闭流同步提升读取效率适配数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;vectorlla(n);ll nums0;ll res0;for(ll i0;in;i){cina[i];if(in-k)numsa[i];else{resmax(res,numsa[i]-a[i-nk]);numsnumsa[i]-a[i-nk];}}coutresendl;return0;}