本文分享的必刷题目是从蓝桥云课、洛谷、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【核心思想】问题分析给定长度为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[i1..n]a[i1..n]各取一段。这是一个线性动态规划的扩展问题。算法选择前缀DPd p 1 [ i ] dp1[i]dp1[i]表示以a [ i ] a[i]a[i]结尾的最大子段和正向后缀DPd 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[i1]dp1[i−1]dp2[i1]的最大值关键步骤特判全负数若所有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[i1] a[i], a[i])dp2[i]max(dp2[i1]a[i],a[i])表示以a [ i ] a[i]a[i]开头的最大子段和枚举删除位置i ii1 ≤ 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[i1]dp2[i1]以i 1 i1i1开头的最大子段更新答案a n s max ( a n s , d p 1 [ i − 1 ] d p 2 [ i 1 ] ) ans \max(ans, dp1[i-1] dp2[i1])ansmax(ans,dp1[i−1]dp2[i1])时间/空间复杂度时间复杂度O ( n ) O(n)O(n)三次线性遍历前缀DP、后缀DP、枚举删除位置空间复杂度O ( n ) O(n)O(n)存储d p 1 dp1dp1和d p 2 dp2dp2数组前后缀DP组合的核心思想问题转化删除一个元素后的最大子段和 左边某段 右边某段两段不相邻前缀预处理快速获取以任意位置结尾的最大子段和后缀预处理快速获取以任意位置开头的最大子段和枚举分割点通过枚举删除位置组合左右两段的最优解适用于区间分割、删除/插入元素后的最优解问题【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;intn,a[N];// n: 数组大小a: 数组元素intdp1[N],dp2[N];// dp1: 从前向后的最大子段和dp2: 从后向前的最大子段和intmain(){cinn;// 读入数组大小boolflag0;// 标记是否存在非负数intmx-1e9;// 记录数组中的最大值for(inti1;in;i){cina[i];// 读入数组元素if(a[i]0)// 如果存在非负数{flag1;}mxmax(mx,a[i]);// 更新最大值}// 如果所有数都是负数则最大子段和就是最大的那个负数if(flag0){coutmxendl;return0;}// 计算从前向后的最大子段和// dp1[i]表示以a[i]结尾的最大子段和dp1[1]a[1];for(inti2;in;i){dp1[i]max(dp1[i-1]a[i],a[i]);}// 计算从后向前的最大子段和// dp2[i]表示以a[i]开头的最大子段和dp2[1]a[n];for(intin;i1;i--)// 这里有个小问题应该是从n-1开始{dp2[i]max(dp2[i1]a[i],a[i]);}intmaxn-1e9;// 记录最大两段子段和for(inti1;in;i){// 计算不相邻的两段最大子段和// 注意这里dp1[i-1]和dp2[i1]分别表示第i个元素左边和右边的最大子段和maxnmax(maxn,dp1[i-1]dp2[i1]);}coutmaxnendl;// 输出结果return0;}【运行结果】5 9 5 -6 -10 7 15
题解：学而思编程 删数最大子段和
本文分享的必刷题目是从蓝桥云课、洛谷、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【核心思想】问题分析给定长度为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[i1..n]a[i1..n]各取一段。这是一个线性动态规划的扩展问题。算法选择前缀DPd p 1 [ i ] dp1[i]dp1[i]表示以a [ i ] a[i]a[i]结尾的最大子段和正向后缀DPd 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[i1]dp1[i−1]dp2[i1]的最大值关键步骤特判全负数若所有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[i1] a[i], a[i])dp2[i]max(dp2[i1]a[i],a[i])表示以a [ i ] a[i]a[i]开头的最大子段和枚举删除位置i ii1 ≤ 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[i1]dp2[i1]以i 1 i1i1开头的最大子段更新答案a n s max ( a n s , d p 1 [ i − 1 ] d p 2 [ i 1 ] ) ans \max(ans, dp1[i-1] dp2[i1])ansmax(ans,dp1[i−1]dp2[i1])时间/空间复杂度时间复杂度O ( n ) O(n)O(n)三次线性遍历前缀DP、后缀DP、枚举删除位置空间复杂度O ( n ) O(n)O(n)存储d p 1 dp1dp1和d p 2 dp2dp2数组前后缀DP组合的核心思想问题转化删除一个元素后的最大子段和 左边某段 右边某段两段不相邻前缀预处理快速获取以任意位置结尾的最大子段和后缀预处理快速获取以任意位置开头的最大子段和枚举分割点通过枚举删除位置组合左右两段的最优解适用于区间分割、删除/插入元素后的最优解问题【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;intn,a[N];// n: 数组大小a: 数组元素intdp1[N],dp2[N];// dp1: 从前向后的最大子段和dp2: 从后向前的最大子段和intmain(){cinn;// 读入数组大小boolflag0;// 标记是否存在非负数intmx-1e9;// 记录数组中的最大值for(inti1;in;i){cina[i];// 读入数组元素if(a[i]0)// 如果存在非负数{flag1;}mxmax(mx,a[i]);// 更新最大值}// 如果所有数都是负数则最大子段和就是最大的那个负数if(flag0){coutmxendl;return0;}// 计算从前向后的最大子段和// dp1[i]表示以a[i]结尾的最大子段和dp1[1]a[1];for(inti2;in;i){dp1[i]max(dp1[i-1]a[i],a[i]);}// 计算从后向前的最大子段和// dp2[i]表示以a[i]开头的最大子段和dp2[1]a[n];for(intin;i1;i--)// 这里有个小问题应该是从n-1开始{dp2[i]max(dp2[i1]a[i],a[i]);}intmaxn-1e9;// 记录最大两段子段和for(inti1;in;i){// 计算不相邻的两段最大子段和// 注意这里dp1[i-1]和dp2[i1]分别表示第i个元素左边和右边的最大子段和maxnmax(maxn,dp1[i-1]dp2[i1]);}coutmaxnendl;// 输出结果return0;}【运行结果】5 9 5 -6 -10 7 15
