题解 | #最大连续子序列#
最大连续子序列
https://www.nowcoder.com/practice/afe7c043f0644f60af98a0fba61af8e7
忽略规范的输入方式,只处理一次
写于2024.3.17,祝复试顺利
#include <iostream> #include <algorithm> using namespace std; const int maxn = 10000; int a[maxn]; int dp[maxn]; // dp[i]组代表以i为结尾的最大连续子序列 int maxsubstr(int n) // 对数组maxsubstr中前n个数进行 找最大连续子序列 { int i; int maximum = 0; for (i = 0; i < n; i++) { if (i == 0) dp[i] = a[i]; else dp[i] = max(a[i], dp[i - 1] + a[i]); // 状态拓展函数 maximum = max(maximum, dp[i]); } return maximum; } int main() { int n, i, answer, zancun, j; scanf("%d", &n); // while (n != 0) // { for (i = 0; i < n; i++) { scanf("%d", &a[i]); } for (i = 0; i < n; i++) { if (a[i] >= 0) break; } if (i == n) // 如果全是负数则输出头尾 { cout << '0' << ' ' << a[0] << ' ' << a[n - 1] << endl; return 0; } // 不全负则继续判断 answer = maxsubstr(n); cout << answer << ' '; for (i = 0; i < n; i++) { if (dp[i] == answer) { zancun = a[i]; break; } } if (a[i] == answer) j = i; else { for (j = i - 1; j >= 0; j--) // 从i-1位置往前找子序列的第一个元素 { zancun += a[j]; if (zancun == answer) { break; } } } cout << a[j] << ' ' << a[i] << endl; // scanf("%d", &n); // cin >> n; // cout << "hdu" << n << endl; // } return 0; }