【题目来源】https://www.luogu.com.cn/problem/P1115【题目描述】给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大。【输入格式】第一行是一个整数表示序列的长度 n。第二行有 n 个整数第 i 个整数表示序列的第 i 个数字 ai。【输出格式】输出一行一个整数表示答案。【输入样例】72 -43 -1 2-4 3【输出样例】4【样例说明】选取 [3,5] 子段 {3,−1,2}其和为 4。【数据规模与约定】对于 40% 的数据保证 n≤2×10^3。对于 100% 的数据保证1≤n≤2×10^5-10^4≤ai≤10^4。【算法分析】● 子序列问题是指在一个序列如数组、字符串等中寻找满足特定条件的子序列的算法问题。子序列指的是从原序列中依序选取的元素组成的新序列但选取的元素不一定连续。● 子序列问题求解的核心思路通过分解子问题利用动态规划或特殊数据结构进行优化。不同变体需要灵活调整状态定义和转移条件‌。● 动态规划定义状态定义‌dp[i] 表示以第 i 个元素结尾的连续子数组的最大和‌。‌目标‌通过比较「当前元素单独成段」和「接上前面子段」两种情况逐步递推全局最大值‌。【算法代码朴素写法】#include bits/stdc.h using namespace std; const int maxn2e55; int a[maxn],dp[maxn]; int ansINT_MIN; int n; int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) { dp[i]max(a[i],dp[i-1]a[i]); } for(int i1; in; i) { ansmax(ans,dp[i]); } coutansendl; return 0; } /* in: 7 2 -4 3 -1 2 -4 3 out: 4 */【算法代码优先队列】#include bits/stdc.h using namespace std; const int maxn2e55; int a[maxn],dp[maxn]; priority_queueint Q; int n; int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) { dp[i]max(a[i],dp[i-1]a[i]); Q.push(dp[i]); } coutQ.top(); return 0; } /* in: 7 2 -4 3 -1 2 -4 3 out: 4 */【参考文献】https://www.luogu.com.cn/problem/solution/P1115https://www.cnblogs.com/zwfymqz/p/6809398.html