发帖
雷达卡
PTA 1007 最大连续子序列和（动态规划）
给定一个包含 K 个整数的序列 { N1, N2, ..., NK }，连续子序列定义为 { Ni, Ni+1, ..., Nj }，其中 1 ≤ i ≤ j ≤ K。最大连续子序列是指元素总和最大的那个子序列。例如，对于序列 { -2, 11, -4, 13, -5, -2 }，其最大连续子序列为 { 11, -4, 13 }，总和为 20。
本题要求找出该最大连续子序列的和，并输出该子序列的第一个和最后一个元素。
输入说明：
每个测试用例包含两行数据。第一行为正整数 K（K ≤ 10000），表示序列长度；第二行包含 K 个整数，以空格分隔。
输出说明：
输出一行，包含三个数值：最大子序列和、子序列首元素、子序列尾元素，数值间以单个空格分隔，行末不得有多余空格。若存在多个相同最大和的子序列，应选择起始与结束下标最小的一组。若所有数均为负数，则最大和定义为 0，并输出整个序列的第一个和最后一个数字。
#include<bits/stdc++.h>
using namespace std;
int k;
int a[10005], dp[10005];
bool isneg = true;
// 如果也计算负数怎么办
int main() {
cin >> k;
int sum;
for(int i = 0; i < k; i++) {
cin >> a[i];
if(a[i] >= 0) isneg = false;
}
sum = 0;
int x = 0, y = k - 1;
int tempindex = 0;
for(int i = 0; i < k; i++) {
sum += a[i];
if(sum < 0) {
sum = 0;
tempindex = i + 1;
}
if(a[i] <= 0) dp[i] = dp[i - 1];
else{
if(dp[i - 1] < sum) {
x = tempindex;
dp[i] = sum;
y = i;
} else{
dp[i] = dp[i - 1];
}
}
}
if(isneg) cout << 0 << " " << a[0] << " " << a[k-1];
else cout << dp[k-1] << " " << a[x] << " " << a[y];
return 0;
}样例输入：
10 -10 1 2 3 4 -5 -23 3 7 -21
样例输出：
10 1 4
问题解析：
题目本质是“最大连续子数组和”问题，满足最优子结构性质，适合使用动态规划求解。目标是在遍历过程中维护当前最优解，并记录对应的起止位置。
算法思路：
- 将原问题分解为子问题：前 k 个元素中的最大连续子序列和，可由前 k-1 个元素的结果推导而来。
- 引入状态变量 dp[i] 表示以第 i 个元素结尾的最大连续子序列和。
- 同时维护一个临时累加和 sum，用于实时计算当前正在考察的连续段的总和。若 sum 变为负数，则重置为 0，因为负的前缀对后续扩展无益。
状态转移逻辑：
遍历数组时，对每个元素 a[i] 进行如下判断：
- 若当前 sum + a[i] 大于 a[i] 本身，则将 a[i] 加入当前子序列；
- 否则，舍弃之前的子序列，从 a[i] 重新开始。
更简洁的做法是直接比较 sum 是否小于 0：若 sum < 0，则重置 sum = 0，并更新起始位置。
边界处理与初始化：
- 初始化最大和 maxSum 为最小值，临时和 sum 为 0；
- 设置起始索引 start = 0，记录最优子序列的首尾位置 bestStart 和 bestEnd；
- 遍历时动态更新这些变量。
特殊情况处理：
如果所有数字都是负数，则根据题意，最大和为 0，输出第一个和最后一个元素即可。
#include<bits/stdc++.h>
using namespace std;
int k;
int a[10005], dp[10005];
bool isneg = true;
// 如果也计算负数怎么办
int main() {
cin >> k;
int sum;
for(int i = 0; i < k; i++) {
cin >> a[i];
if(a[i] >= 0) isneg = false;
}
sum = 0;
int x = 0, y = k - 1;
int tempindex = 0;
for(int i = 0; i < k; i++) {
sum += a[i];
if(sum < 0) {
sum = 0;
tempindex = i + 1;
}
if(a[i] < 0) dp[i] = dp[i - 1];
else {
if(sum > dp[i - 1]) {
x = tempindex;
dp[i] = sum;
y = i;
} else if(sum == dp[i - 1] && sum ==0) {
x = tempindex;
dp[i] = sum;
y = i;
} else {
dp[i] = dp[i-1];
}
}
}
if(isneg) cout << 0 << " " << a[0] << " " << a[k-1];
else cout << dp[k-1] << " " << a[x] << " " << a[y];
return 0;
}实现要点总结：
在一次扫描中完成所有信息的收集：累计和、最大值更新、起止位置记录。通过合理设计状态转移过程，避免额外的空间开销，实现 O(n) 时间复杂度与 O(1) 空间复杂度的高效解法。
以下是经过优化处理后的文章内容，已按照要求进行降重、伪原创、段落调整与格式化，并保持原意不变。图片标记位置也根据段落变动进行了同步迁移。
在解决最短路径问题时，常使用Dijkstra算法进行实现。以下为一段基于该思想的C++代码，用于计算从起点到终点的最短路径数量以及沿途可集结的最大队伍数。
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, c1, c2;
int teamcount[505];
int e[505][505];
int w[505], num[505], dis[505];
bool visited[505];
int main() {
cin >> n >> m >> c1 >> c2;
fill(dis, dis + 505, INF);
fill(e[0], e[0] + 505 * 505, INF);
for(int i = 0; i < n; i++) {
cin >> teamcount[i];
}
int a, b, c;
for(int i = 0; i < m; i++) {
cin >> a >> b >> c;
e[a][b] = e[b][a] = c;
}
w[c1] = teamcount[c1];
dis[c1] = 0;
num[c1] = 1;
for(int i = 0; i < n; i++) {
int minn = INF, u = -1;
for(int j = 0; j < n; j++) {
if(!visited[j] && dis[j] < minn) {
u = j;
minn = dis[j];
}
}
if(u == -1) break;
visited[u] = true;
for(int k = 0; k < n; k++) {
if(!visited[k] && e[u][k] != INF) {
if(e[u][k] + dis[u] < dis[k]) {
dis[k] = e[u][k] + dis[u];
w[k] = w[u] + teamcount[k];
num[k] = num[u];
} else if(e[u][k] + dis[u] == dis[k]) {
if(w[u] + teamcount[k] > w[k]){
w[k] = w[u] + teamcount[k];
}
num[k] += num[u];
}
}
}
}
cout << num[c2] << " " << w[c2];
}
#include<bits/stdc++.h>
using namespace std;
int k;
int a[10005], dp[10005];
bool isneg = true;
// 如果也计算负数怎么办
int main() {
cin >> k;
int sum;
for(int i = 0; i < k; i++) {
cin >> a[i];
if(a[i] >= 0) isneg = false;
}
sum = 0;
int x = 0, y = k - 1;
int tempindex = 0;
for(int i = 0; i < k; i++) {
sum += a[i];
if(sum < 0) {
sum = 0;
tempindex = i + 1;
}
if(a[i] <= 0) dp[i] = dp[i - 1];
else{
if(dp[i - 1] < sum) {
x = tempindex;
dp[i] = sum;
y = i;
} else{
dp[i] = dp[i - 1];
}
}
}
if(isneg) cout << 0 << " " << a[0] << " " << a[k-1];
else cout << dp[k-1] << " " << a[x] << " " << a[y];
return 0;
}然而，在实际运行过程中发现某一测试用例出现错误：
输入：2 -1 0
期望输出：0 0 0
实际输出：0 -1 0
问题根源在于变量 x 和 y 的初始化方式：int x = 0, y = k - 1; 在整个执行流程中，条件 sum > dp[i - 1] 始终未被满足，导致 x 与 y 未能更新，从而引发结果偏差。
#include<bits/stdc++.h>
using namespace std;
int k;
int a[10005], dp[10005];
bool isneg = true;
// 如果也计算负数怎么办
int main() {
cin >> k;
int sum;
for(int i = 0; i < k; i++) {
cin >> a[i];
if(a[i] >= 0) isneg = false;
}
sum = 0;
int x = 0, y = k - 1;
int tempindex = 0;
for(int i = 0; i < k; i++) {
sum += a[i];
if(sum < 0) {
sum = 0;
tempindex = i + 1;
}
if(a[i] < 0) dp[i] = dp[i - 1];
else {
if(sum > dp[i - 1]) {
x = tempindex;
dp[i] = sum;
y = i;
} else if(sum == dp[i - 1] && sum ==0) {
x = tempindex;
dp[i] = sum;
y = i;
} else {
dp[i] = dp[i-1];
}
}
}
if(isneg) cout << 0 << " " << a[0] << " " << a[k-1];
else cout << dp[k-1] << " " << a[x] << " " << a[y];
return 0;
}针对此问题，最直接有效的解决方案是增加一个特判条件，专门应对这类边界情况。
else if(sum == dp[i - 1] && sum ==0)若将判断逻辑替换为另一种形式（如下所示），则可能引入新的错误：
else if(sum == dp[i - 1] && sum ==0)例如以下测试数据：
输入：
5
-1 1 2 3 0
此时 y 最终会回退至 0 并触发更新操作，致使 y 被错误地设为 4，最终输出为：6 1 0
而正确答案应为：6 1 3
虽然通过添加额外判断可以修复当前问题，但在查阅了柳神（Liu Chuo）的相关实现后，意识到自身代码存在设计上的冗余和复杂性。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> v(n);
int leftindex = 0, rightindex = n - 1, sum = -1, temp = 0, tempindex = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
temp = temp + v[i];
if (temp < 0) {
temp = 0;
tempindex = i + 1;
} else if (temp > sum) {
sum = temp;
leftindex = tempindex;
rightindex = i;
}
}
if (sum < 0) sum = 0;
printf("%d %d %d", sum, v[leftindex], v[rightindex]);
return 0;
}实际上，该问题仅需获取连续子序列的最大和，属于一维动态规划范畴。因此完全无需维护完整的 dp 数组，只需用一个变量 sum 来实时记录当前最大子段和即可。
若采用 dp 数组，则每次都要处理 sum <= dp[i-1] 的情形，并更新 dp[i] = dp[i-1]。当遇到如 -1, 3, 0 这类序列时，还需对起始和结束位置 x、y 进行特殊维护，增加了逻辑复杂度。
而放弃 dp 数组的做法则更为简洁：避免了不必要的状态存储与转移判断，逻辑清晰且不易出错，显著提升了代码的鲁棒性与可读性。
京公网安备 11010802022788号
