题解：学而思编程 删数最大子段和

本文分享的必刷题目是从蓝桥云课、洛谷、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的序列a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​，需要删除一个元素后，求剩余数组的最大子段和。等价于求两段不相邻的最大子段和（删除位置i ii后，左边a [ 1.. i − 1 ] a[1..i-1]a[1..i−1]和右边a [ i + 1.. n ] a[i+1..n]a[i+1..n]各取一段）。这是一个线性动态规划的扩展问题。

2. 算法选择：

   • 前缀DP：d p 1 [ i ] dp1[i]dp1[i]表示以a [ i ] a[i]a[i]结尾的最大子段和（正向）
   • 后缀DP：d p 2 [ i ] dp2[i]dp2[i]表示以a [ i ] a[i]a[i]开头的最大子段和（反向）
   • 组合枚举：枚举删除位置i ii，计算d p 1 [ i − 1 ] + d p 2 [ i + 1 ] dp1[i-1] + dp2[i+1]dp1[i−1]+dp2[i+1]的最大值

3. 关键步骤：

   • 特判全负数：若所有a [ i ] < 0 a[i] < 0a[i]<0，答案为max ⁡ ( a [ i ] ) \max(a[i])max(a[i])（只能选最大的负数）
   • 计算前缀最大子段和：
     • d p 1 [ i ] = max ⁡ ( d p 1 [ i − 1 ] + a [ i ] , a [ i ] ) dp1[i] = \max(dp1[i-1] + a[i], a[i])dp1[i]=max(dp1[i−1]+a[i],a[i])
     • 表示以a [ i ] a[i]a[i]结尾的最大子段和
   • 计算后缀最大子段和：
     • d p 2 [ i ] = max ⁡ ( d p 2 [ i + 1 ] + a [ i ] , a [ i ] ) dp2[i] = \max(dp2[i+1] + a[i], a[i])dp2[i]=max(dp2[i+1]+a[i],a[i])
     • 表示以a [ i ] a[i]a[i]开头的最大子段和
   • 枚举删除位置i ii（1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n）：
     • 左边最大贡献：d p 1 [ i − 1 ] dp1[i-1]dp1[i−1]（以i − 1 i-1i−1结尾的最大子段）
     • 右边最大贡献：d p 2 [ i + 1 ] dp2[i+1]dp2[i+1]（以i + 1 i+1i+1开头的最大子段）
     • 更新答案：a n s = max ⁡ ( a n s , d p 1 [ i − 1 ] + d p 2 [ i + 1 ] ) ans = \max(ans, dp1[i-1] + dp2[i+1])ans=max(ans,dp1[i−1]+dp2[i+1])

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，三次线性遍历（前缀DP、后缀DP、枚举删除位置）
   • 空间复杂度：O ( n ) O(n)O(n)，存储d p 1 dp1dp1和d p 2 dp2dp2数组

5. 前后缀DP组合的核心思想：

   • 问题转化：删除一个元素后的最大子段和 = 左边某段 + 右边某段（两段不相邻）
   • 前缀预处理：快速获取以任意位置结尾的最大子段和
   • 后缀预处理：快速获取以任意位置开头的最大子段和
   • 枚举分割点：通过枚举删除位置，组合左右两段的最优解
   • 适用于区间分割、删除/插入元素后的最优解问题

【算法标签】

#线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;intn,a[N];// n: 数组大小，a: 数组元素intdp1[N],dp2[N];// dp1: 从前向后的最大子段和，dp2: 从后向前的最大子段和intmain(){cin>>n;// 读入数组大小boolflag=0;// 标记是否存在非负数intmx=-1e9;// 记录数组中的最大值for(inti=1;i<=n;i++){cin>>a[i];// 读入数组元素if(a[i]>=0)// 如果存在非负数{flag=1;}mx=max(mx,a[i]);// 更新最大值}// 如果所有数都是负数，则最大子段和就是最大的那个负数if(flag==0){cout<<mx<<endl;return0;}// 计算从前向后的最大子段和// dp1[i]表示以a[i]结尾的最大子段和dp1[1]=a[1];for(inti=2;i<=n;i++){dp1[i]=max(dp1[i-1]+a[i],a[i]);}// 计算从后向前的最大子段和// dp2[i]表示以a[i]开头的最大子段和dp2[1]=a[n];for(inti=n;i>=1;i--)// 这里有个小问题，应该是从n-1开始{dp2[i]=max(dp2[i+1]+a[i],a[i]);}intmaxn=-1e9;// 记录最大两段子段和for(inti=1;i<=n;i++){// 计算不相邻的两段最大子段和// 注意：这里dp1[i-1]和dp2[i+1]分别表示第i个元素左边和右边的最大子段和maxn=max(maxn,dp1[i-1]+dp2[i+1]);}cout<<maxn<<endl;// 输出结果return0;}

【运行结果】

5 9 5 -6 -10 7 15