题目链接
https://www.patest.cn/contests/pat-a-practise/1007
思路 最大子列和 就是 一直往后加 如果 sum < 0 就重置为 0 然后每次 判断一下 sum 是否 > ans 如果是 就更新 然后 为什么这样是对的
就是 假设 当前数字是最大子串和 我们如何知道 前面的求和结果 要不要放入当前子串中 如果前面的求和结果 < 0 的话 那么对当前子串 是没有贡献的 所以就不要
然后 我们需要记录 子串的起始位置 就可以了 因为 更新答案的时候 当前位置 就是结束位置
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e4 + 5; const int MOD = 1e9 + 7; int arr[maxn]; int main() { int n; cin >> n; int l, r, ans = -1, num, temp = 0, vis, flag = 0; for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); if (i == 0 || flag) { vis = arr[i]; flag = 0; } temp += arr[i]; if (temp < 0) { temp = 0; flag = 1; continue; } if (temp > ans) { ans = temp; l = vis; r = arr[i]; } } if (ans != -1) printf("%d %d %d\n", ans, l, r); else printf("%d %d %d\n", 0, arr[0], arr[n - 1]); }转载于:https://www.cnblogs.com/Dup4/p/9433197.html
