当前位置：首页 > news >正文

题解：学而思编程删除一个元素

news 2026/6/22 20:06:23

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：删除一个元素

【题目描述】

给出一个数组a 1 , a 2 , ⋯ , a n a_1,a_2,⋯,a_na1,a2,⋯,an，删除一个元素后，求它的最大子段和。（子段是指数组中连续的一段元素）

删除的元素可以由你自由选择，但是不能不删除任何元素，输出你能得到的最大的子段和。

【输入】

第1 11行，1 11个正整数n nn。

第2 22行，n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,⋯,a_na1,a2,⋯,an。

【输出】

输出能得到的最大的子段和。

【输入样例】

5 9 5 -6 -10 7

【输出样例】

【核心思想】

问题分析：给定长度为n nn的数组，需要恰好删除一个元素后，求剩余数组的最大子段和。这是一个线性DP问题，关键在于如何高效计算删除某个位置后的最大子段和。
算法选择：
- 正向DP：f [ i ] f[i]f[i]表示以位置i ii结尾的最大子段和
  - 转移方程：f [ i ] = max ⁡ ( f [ i − 1 ] + a [ i ] , a [ i ] ) f[i] = \max(f[i-1] + a[i], a[i])f[i]=max(f[i−1]+a[i],a[i])
- 反向DP：g [ i ] g[i]g[i]表示以位置i ii开头的最大子段和
  - 转移方程：g [ i ] = max ⁡ ( g [ i + 1 ] + a [ i ] , a [ i ] ) g[i] = \max(g[i+1] + a[i], a[i])g[i]=max(g[i+1]+a[i],a[i])
- 枚举分割点：对于每个删除位置i ii，最优解为max ⁡ ( f [ i − 1 ] + g [ i + 1 ] , f [ i − 1 ] , g [ i + 1 ] ) \max(f[i-1] + g[i+1], f[i-1], g[i+1])max(f[i−1]+g[i+1],f[i−1],g[i+1])
关键步骤：
- 读取输入：n nn（数组长度）、a [ 1.. n ] a[1..n]a[1..n]（数组元素）
- 初始化：f ff和g gg数组初始化为极小值
- 正向DP（i ii从1 11到n nn）：
  - f [ i ] = max ⁡ ( f [ i − 1 ] + a [ i ] , a [ i ] ) f[i] = \max(f[i-1] + a[i], a[i])f[i]=max(f[i−1]+a[i],a[i])
- 反向DP（i ii从n nn到1 11）：
  - g [ i ] = max ⁡ ( g [ i + 1 ] + a [ i ] , a [ i ] ) g[i] = \max(g[i+1] + a[i], a[i])g[i]=max(g[i+1]+a[i],a[i])
- 枚举删除位置（i ii从1 11到n nn）：
  - 计算三种情况：左段+右段、仅左段、仅右段
  - a n s = max ⁡ ( a n s , f [ i − 1 ] + g [ i + 1 ] , f [ i − 1 ] , g [ i + 1 ] ) ans = \max(ans, f[i-1] + g[i+1], f[i-1], g[i+1])ans=max(ans,f[i−1]+g[i+1],f[i−1],g[i+1])
- 输出结果：最大子段和a n s ansans
时间/空间复杂度：
- 时间复杂度：O ( n ) O(n)O(n)，三次线性遍历
- 空间复杂度：O ( n ) O(n)O(n)，存储f ff和g gg数组
线性DP的核心思想：
- 正向与反向预处理：通过两次DP分别预处理以每个位置结尾/开头的最大子段和
- 分割点枚举：删除位置将数组分为左右两段，预处理后可以O ( 1 ) O(1)O(1)计算每段的最优值
- 状态转移：最大子段和要么接在前一段后面，要么重新开始
- 边界处理：注意i = 1 i=1i=1和i = n i=ni=n时的边界情况
- 适用于子段和问题、分割点优化、前后缀预处理类问题

【算法标签】

#线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义长整型别名，便于处理大数据#defineintlonglong// ================= 常量与全局变量 =================constintN=100005;// 数组最大长度intn;// 数组长度inta[N];// 原始数组intf[N];// f[i] 表示以 i 结尾的最大子段和intg[N];// g[i] 表示以 i 开头的最大子段和intans=-1e18;// 最终答案，初始化为极小值// ================= 主函数 =================signedmain(){// 读取数组长度cin>>n;// 读取数组元素for(inti=1;i<=n;i++)cin>>a[i];// 初始化 f 和 g 数组为极小值memset(f,-0x3f,sizeof(f));memset(g,-0x3f,sizeof(g));// ========= 正向 DP：计算以 i 结尾的最大子段和 =========f[1]=a[1];// 第一个元素单独成段for(inti=2;i<=n;i++)f[i]=max(f[i-1]+a[i],a[i]);// 要么接在前一段后面，要么重新开始// ========= 反向 DP：计算以 i 开头的最大子段和 =========g[n]=a[n];// 最后一个元素单独成段for(inti=n-1;i>=1;i--)g[i]=max(g[i+1]+a[i],a[i]);// 要么接在后一段前面，要么重新开始// ========= 枚举分割点，计算不相交的两段的最大和 =========for(inti=1;i<=n;i++){// 取三种情况的最大值：// 1. 左段以 i-1 结尾 + 右段以 i+1 开头// 2. 只有左段// 3. 只有右段ans=max({ans,f[i-1]+g[i+1],f[i-1],g[i+1]});}// 输出结果cout<<ans<<endl;return0;}