企业官网建设流程全解析

【题目来源】
https://www.luogu.com.cn/problem/P1115

【题目描述】
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

【输入格式】
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。

【输出格式】
输出一行一个整数表示答案。

【输入样例】
7
2 -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 maxn=2e5+5; int a[maxn],dp[maxn]; int ans=INT_MIN; int n; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) { dp[i]=max(a[i],dp[i-1]+a[i]); } for(int i=1; i<=n; i++) { ans=max(ans,dp[i]); } cout<<ans<<endl; return 0; } /* in: 7 2 -4 3 -1 2 -4 3 out: 4 */

【算法代码：优先队列】

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; int a[maxn],dp[maxn]; priority_queue<int> Q; int n; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) { dp[i]=max(a[i],dp[i-1]+a[i]); Q.push(dp[i]); } cout<<Q.top(); return 0; } /* in: 7 2 -4 3 -1 2 -4 3 out: 4 */

【参考文献】
https://www.luogu.com.cn/problem/solution/P1115
https://www.cnblogs.com/zwfymqz/p/6809398.html