当前位置：首页 > news >正文

题解：洛谷 U327333 Max Sum Plus Plus 2

news 2026/5/22 17:45:17

本文分享的必刷题目是从蓝桥云课、洛谷、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

【输出样例】

【算法标签】

#未分级 #线性DP-一维

【代码详解】

// 30分版本#include<bits/stdc++.h>usingnamespacestd;constintN=1005,INF=1e9;intn,m,temp;// n: 数字个数，m: 子段个数，temp: 临时变量ints[N],f[N][N],premax[N][N];// s: 数字序列，f: DP数组，premax: 前缀最大值数组intmain(){while(cin>>m>>n)// 处理多个测试用例，直到文件结束{for(inti=1;i<=n;i++)cin>>s[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti=1;i<=m;i++)// 遍历子段个数，从1到m{temp=-INF;// 初始化temp为负无穷for(intj=i;j<=n;j++)// 遍历结束位置，从i到n{if(j==i)// 如果当前是第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];// 状态转移方程temp=max(temp,f[i][j]);// 更新当前最大f值premax[i][j]=max(premax[i][j],temp);// 更新前缀最大值}}cout<<temp<<endl;// 输出结果}return0;}

// 40分版本#include<bits/stdc++.h>usingnamespacestd;constintN=5005,INF=1e9;intn,m,temp;// n: 数字个数，m: 子段个数，temp: 临时变量ints[N],f[N][N],premax[N];// s: 数字序列，f: DP数组，premax: 前缀最大值数组（一维优化）intmain(){while(cin>>m>>n)// 处理多个测试用例，直到文件结束{for(inti=1;i<=n;i++)cin>>s[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti=1;i<=m;i++)// 遍历子段个数，从1到m{temp=-INF;// 初始化temp为负无穷for(intj=i;j<=n;j++)// 遍历结束位置，从i到n{if(j==i)// 如果当前是第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数组，存储上一轮的最大值temp=max(temp,f[i][j]);// 更新当前最大f值}}cout<<temp<<endl;// 输出结果}return0;}

// AC版本#include<bits/stdc++.h>usingnamespacestd;constintN=1000005,INF=1e9;intn,m,temp;// n: 数字个数，m: 子段个数，temp: 临时变量ints[N],f[N],premax[N];// s: 数字序列，f: DP数组（滚动数组），premax: 前缀最大值数组intmain(){while(cin>>m>>n)// 处理多个测试用例，直到文件结束{for(inti=1;i<=n;i++)cin>>s[i];// 输入数字序列memset(f,0,sizeof(f));// 初始化DP数组为0memset(premax,0,sizeof(premax));// 初始化前缀最大值数组为0for(inti=1;i<=m;i++)// 遍历子段个数，从1到m{temp=-INF;// 初始化temp为负无穷for(intj=i;j<=n;j++)// 遍历结束位置，从i到n{f[j]=max(premax[j-1],f[j-1])+s[j];// 状态转移方程premax[j-1]=temp;// 更新premax数组，存储上一轮的最大值temp=max(temp,f[j]);// 更新当前最大f值}}cout<<temp<<endl;// 输出结果}return0;}