HDU 1231最大连续子序列（周赛F题）

本文主要是介绍HDU 1231最大连续子序列（周赛F题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题挺气人的，比赛的时候编了提交了好多次都不知道哪里错了，搞了两天才知道自己的代码哪里错了看了队友的发现他的方法确实很好，参考他的方法……我试了用了下DP，但是就是提交不过，真的晕死……

下面给出时间复杂度最低和第二低的算法，第一种为累计求和，时间复杂度为o(n)

#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int main()
{int n;while(scanf("%d",&n)&&n){int a[10005],i,j=0,max=-1,sum=0,end,start=0,s,e;for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++){if(a[i]>=0) j=1;sum+=a[i];end=i;if(sum<0){sum=0;start=i+1;end=i+1;}if(max<sum){max=sum;s=start;e=end;}}if(j) printf("%d %d %d\n",max,a[s],a[e]);else printf("0 %d %d\n",a[0],a[n-1]);}return 0;
}

第二种为分治法，时间复杂度为0（n*logn)

#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int MAXN = 10010;
struct ANS
{int sum;int l, r;ANS() {}ANS(int a, int b, int c) : sum(a), l(b), r(c) {}
};
ANS maxsum(int* a, int x, int y)
{int m, v, L, R, l, r;ANS M(a[x], a[x], a[x]), t1, t2;if (y - x == 1)return M;m = x + (y - x) / 2;t1 = maxsum(a, x, m);t2 = maxsum(a, m, y);if (t1.sum >= t2.sum) M = t1;else M = t2;v = 0;L = a[m - 1];l = a[m - 1];for (int i = m - 1; i >= x; i--){v += a[i];if (v > L) L = v, l = a[i];}v = 0;R = a[m];r = a[m];for (int i = m; i < y; i++){v += a[i];if (v > R) R = v, r = a[i];}if (M.sum > (L + R))return M;return ANS(L + R, l, r);
}int k, a[MAXN];
int main()
{while (scanf("%d", &k) && k){for(int i=0;i<k;i++)scanf("%d", &a[i]);ANS ans = maxsum(a, 0, k);if (ans.sum >= 0)printf("%d %d %d\n", ans.sum, ans.l, ans.r);elseprintf("0 %d %d\n", a[0], a[k - 1]);}return 0;
}

这篇关于HDU 1231最大连续子序列（周赛F题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---