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

本文分享的必刷题目是从蓝桥云课、洛谷、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

【输出样例】

15

【核心思想】

1. 问题分析：给定长度为n nn的数组，需要恰好删除一个元素后，求剩余数组的最大子段和。这是一个线性DP问题，关键在于如何高效计算删除某个位置后的最大子段和。

2. 算法选择：

   • 正向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])

3. 关键步骤：

   • 读取输入：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

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，三次线性遍历
   • 空间复杂度：O ( n ) O(n)O(n)，存储f ff和g gg数组

5. 线性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;}

【运行结果】