题解：洛谷 U327333 Max Sum Plus Plus 2

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷U327333 Max Sum Plus Plus 2 - 洛谷【题目描述】无【输入】你有n nn个数s 1 s_1s1​,s 2 s_2s2​…s n s_nsn​给你一个整数m mm求m mm个子段和的最大值注意子段和指的是连续几个数字的和。【输出】输入m mm输入n nn。后面跟着输入n nn个a i a_iai​。【输入样例】2 6 -1 4 -2 3 -2 3【输出样例】8【算法标签】#未分级 #线性DP-一维【代码详解】// 30分版本#includebits/stdc.husingnamespacestd;constintN1005,INF1e9;intn,m,temp;// n: 数字个数m: 子段个数temp: 临时变量ints[N],f[N][N],premax[N][N];// s: 数字序列f: DP数组premax: 前缀最大值数组intmain(){while(cinmn)// 处理多个测试用例直到文件结束{for(inti1;in;i)cins[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti1;im;i)// 遍历子段个数从1到m{temp-INF;// 初始化temp为负无穷for(intji;jn;j)// 遍历结束位置从i到n{if(ji)// 如果当前是第i个子段的第一个元素f[i][j]f[i-1][j-1]s[i];// 只能将s[i]作为新的子段else// 如果当前不是第i个子段的第一个元素f[i][j]max(f[i][j-1],premax[i-1][j-1])s[j];// 状态转移方程tempmax(temp,f[i][j]);// 更新当前最大f值premax[i][j]max(premax[i][j],temp);// 更新前缀最大值}}couttempendl;// 输出结果}return0;}// 40分版本#includebits/stdc.husingnamespacestd;constintN5005,INF1e9;intn,m,temp;// n: 数字个数m: 子段个数temp: 临时变量ints[N],f[N][N],premax[N];// s: 数字序列f: DP数组premax: 前缀最大值数组一维优化intmain(){while(cinmn)// 处理多个测试用例直到文件结束{for(inti1;in;i)cins[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti1;im;i)// 遍历子段个数从1到m{temp-INF;// 初始化temp为负无穷for(intji;jn;j)// 遍历结束位置从i到n{if(ji)// 如果当前是第i个子段的第一个元素f[i][j]f[i-1][j-1]s[i];// 只能将s[i]作为新的子段else// 如果当前不是第i个子段的第一个元素f[i][j]max(f[i][j-1],premax[j-1])s[j];// 状态转移方程premax[j-1]temp;// 更新premax数组存储上一轮的最大值tempmax(temp,f[i][j]);// 更新当前最大f值}}couttempendl;// 输出结果}return0;}// AC版本#includebits/stdc.husingnamespacestd;constintN1000005,INF1e9;intn,m,temp;// n: 数字个数m: 子段个数temp: 临时变量ints[N],f[N],premax[N];// s: 数字序列f: DP数组滚动数组premax: 前缀最大值数组intmain(){while(cinmn)// 处理多个测试用例直到文件结束{for(inti1;in;i)cins[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti1;im;i)// 遍历子段个数从1到m{temp-INF;// 初始化temp为负无穷for(intji;jn;j)// 遍历结束位置从i到n{f[j]max(premax[j-1],f[j-1])s[j];// 状态转移方程premax[j-1]temp;// 更新premax数组存储上一轮的最大值tempmax(temp,f[j]);// 更新当前最大f值}}couttempendl;// 输出结果}return0;}【运行结果】2 6 -1 4 -2 3 -2 3 8