题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1003
题意 给出一个序列 要求找出一个和最大的子序列
思路 O（N）的做法 但是要标记 子序列的头部位置 如果输入全部是负数的话 应该输出是最小的负数和它的位置 而不是输出0 0 0
AC代码
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<string> #include<list> #include<stack> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 5; int main() { int t; cin >> t; int count = 1; while (t--) { int n; scanf("%d", &n); int num; int flag = 1; int tot = 0; int ans = -1000; int start = 0, end = 0; for (int i = 1; i <= n; i++) { scanf("%d", &num); tot += num; if (tot > ans) { ans = tot; start = flag; end = i; } if (tot < 0) { tot = 0; flag = i + 1; } } printf("Case %d:\n", count++); printf("%d %d %d\n", ans, start, end); if (t != 0) cout << endl; } return 0; }转载于:https://www.cnblogs.com/Dup4/p/9433106.html
