本文分享的必刷题目是从蓝桥云课、洛谷、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的数组需要恰好删除一个元素后求剩余数组的最大子段和。这是一个线性DP问题关键在于如何高效计算删除某个位置后的最大子段和。算法选择正向DPf [ 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])反向DPg [ i ] g[i]g[i]表示以位置i ii开头的最大子段和转移方程g [ i ] max ⁡ ( g [ i 1 ] a [ i ] , a [ i ] ) g[i] \max(g[i1] a[i], a[i])g[i]max(g[i1]a[i],a[i])枚举分割点对于每个删除位置i ii最优解为max ⁡ ( f [ i − 1 ] g [ i 1 ] , f [ i − 1 ] , g [ i 1 ] ) \max(f[i-1] g[i1], f[i-1], g[i1])max(f[i−1]g[i1],f[i−1],g[i1])关键步骤读取输入n nn数组长度、a [ 1.. n ] a[1..n]a[1..n]数组元素初始化f ff和g gg数组初始化为极小值正向DPi ii从1 11到n nnf [ 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])反向DPi ii从n nn到1 11g [ i ] max ⁡ ( g [ i 1 ] a [ i ] , a [ i ] ) g[i] \max(g[i1] a[i], a[i])g[i]max(g[i1]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[i1], f[i-1], g[i1])ansmax(ans,f[i−1]g[i1],f[i−1],g[i1])输出结果最大子段和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 i1i1和i n inin时的边界情况适用于子段和问题、分割点优化、前后缀预处理类问题【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;// 定义长整型别名便于处理大数据#defineintlonglong// 常量与全局变量 constintN100005;// 数组最大长度intn;// 数组长度inta[N];// 原始数组intf[N];// f[i] 表示以 i 结尾的最大子段和intg[N];// g[i] 表示以 i 开头的最大子段和intans-1e18;// 最终答案初始化为极小值// 主函数 signedmain(){// 读取数组长度cinn;// 读取数组元素for(inti1;in;i)cina[i];// 初始化 f 和 g 数组为极小值memset(f,-0x3f,sizeof(f));memset(g,-0x3f,sizeof(g));// 正向 DP计算以 i 结尾的最大子段和 f[1]a[1];// 第一个元素单独成段for(inti2;in;i)f[i]max(f[i-1]a[i],a[i]);// 要么接在前一段后面要么重新开始// 反向 DP计算以 i 开头的最大子段和 g[n]a[n];// 最后一个元素单独成段for(intin-1;i1;i--)g[i]max(g[i1]a[i],a[i]);// 要么接在后一段前面要么重新开始// 枚举分割点计算不相交的两段的最大和 for(inti1;in;i){// 取三种情况的最大值// 1. 左段以 i-1 结尾 右段以 i1 开头// 2. 只有左段// 3. 只有右段ansmax({ans,f[i-1]g[i1],f[i-1],g[i1]});}// 输出结果coutansendl;return0;}【运行结果】