本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来,并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构,旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏:算法题解:C++与Python实现!
附上汇总贴:算法竞赛备考冲刺必刷题(C++) | 汇总
【题目来源】
学而思编程:删数最大子段和
【题目描述】
给出一个数组
a
1
,
a
2
,
⋯
,
a
n
a_1,a_2,⋯ ,a_n
a1,a2,⋯ ,an,删除一个元素后,求它的最大子段和。(子段是指数组中连续的一段元素)
删除的元素可以由你自由选择,但是不能不删除任何元素,输出你能得到的最大的子段和。
【输入】
第
1
1
1 行,
1
1
1 个正整数
n
n
n。
第
2
2
2 行,
n
n
n 个整数
a
1
,
a
2
,
⋯
,
a
n
a_1,a_2,⋯ ,a_n
a1,a2,⋯ ,an。
【输出】
输出能得到的最大的子段和。
【输入样例】
5
9 5 -6 -10 7
【输出样例】
15
【核心思想】
问题分析:给定长度为
n
n
n 的序列
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \\ldots, a_n
a1,a2,…,an,需要删除一个元素后,求剩余数组的最大子段和。等价于求两段不相邻的最大子段和(删除位置
i
i
i 后,左边
a
[
1..
i
−
1
]
a[1..i-1]
a[1..i−1] 和右边
a
[
i
+
1..
n
]
a[i+1..n]
a[i+1..n] 各取一段)。这是一个线性动态规划的扩展问题。
算法选择:
- 前缀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
i
i,计算d
p
1
[
i
−
1
]
+
d
p
2
[
i
+
1
]
dp1[i-1] + dp2[i+1]
dp1[i−1]+dp2[i+1] 的最大值
关键步骤:
- 特判全负数:若所有
a
[
i
]
<
0
a[i] < 0
a[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
i
i(1
≤
i
≤
n
1 \\leq i \\leq n
1≤i≤n):- 左边最大贡献:
d
p
1
[
i
−
1
]
dp1[i-1]
dp1[i−1](以i
−
1
i-1
i−1 结尾的最大子段) - 右边最大贡献:
d
p
2
[
i
+
1
]
dp2[i+1]
dp2[i+1](以i
+
1
i+1
i+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])
- 左边最大贡献:
时间/空间复杂度:
- 时间复杂度:
O
(
n
)
O(n)
O(n),三次线性遍历(前缀DP、后缀DP、枚举删除位置) - 空间复杂度:
O
(
n
)
O(n)
O(n),存储d
p
1
dp1
dp1 和d
p
2
dp2
dp2 数组
前后缀DP组合的核心思想:
- 问题转化:删除一个元素后的最大子段和 = 左边某段 + 右边某段(两段不相邻)
- 前缀预处理:快速获取以任意位置结尾的最大子段和
- 后缀预处理:快速获取以任意位置开头的最大子段和
- 枚举分割点:通过枚举删除位置,组合左右两段的最优解
- 适用于区间分割、删除/插入元素后的最优解问题
【算法标签】
#线性DP-一维
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, a[N]; // n: 数组大小,a: 数组元素
int dp1[N], dp2[N]; // dp1: 从前向后的最大子段和,dp2: 从后向前的最大子段和
int main()
{
cin >> n; // 读入数组大小
bool flag = 0; // 标记是否存在非负数
int mx = –1e9; // 记录数组中的最大值
for (int i = 1; i <= n; i++)
{
cin >> a[i]; // 读入数组元素
if (a[i] >= 0) // 如果存在非负数
{
flag = 1;
}
mx = max(mx, a[i]); // 更新最大值
}
// 如果所有数都是负数,则最大子段和就是最大的那个负数
if (flag == 0)
{
cout << mx << endl;
return 0;
}
// 计算从前向后的最大子段和
// dp1[i]表示以a[i]结尾的最大子段和
dp1[1] = a[1];
for (int i = 2; i <= n; i++)
{
dp1[i] = max(dp1[i – 1] + a[i], a[i]);
}
// 计算从后向前的最大子段和
// dp2[i]表示以a[i]开头的最大子段和
dp2[1] = a[n];
for (int i = n; i >= 1; i—) // 这里有个小问题,应该是从n-1开始
{
dp2[i] = max(dp2[i + 1] + a[i], a[i]);
}
int maxn = –1e9; // 记录最大两段子段和
for (int i = 1; i <= n; i++)
{
// 计算不相邻的两段最大子段和
// 注意:这里dp1[i-1]和dp2[i+1]分别表示第i个元素左边和右边的最大子段和
maxn = max(maxn, dp1[i – 1] + dp2[i + 1]);
}
cout << maxn << endl; // 输出结果
return 0;
}
【运行结果】
5
9 5 -6 -10 7
15

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

