C++代码
- /*
- Title: 最大连续子序列
- Problem URL: http://acm.hdu.edu.cn/showproblem.php?pid=1231
- Author: Moqi
- Date: 2008-03-19
- Description:505951 2008-03-19 22:42:40 Accepted 1231 203MS 0K 857B C moqi
- */
- #include <stdio.h>
- int main()
- {
- int i, k, n, max, sumk, flag;
- int s[10001], sum[10001], a[10001];
- while (scanf ("%d", &n))
- {
- flag = 0;
- if (n == 0)
- break;
- sumk = k = max = 0;
- for (i = 0; i < n; i++)
- {
- scanf("%d", &s[i]);
- if (s[i] >= 0)
- flag = 1;
- if (sumk >= 0)
- {
- sumk += s[i];
- a[i] = k;
- }
- else
- {
- sumk = s[i];
- a[i] = k = i;
- }
- sum[i] = sumk;
- if (sumk > max)
- max = sumk;
- }
- if (flag == 0)
- printf("%d %d %d\n", 0, s[0], s[n-1]);
- else
- {
- k = 0;
- for (i = 1; i < n; i++)
- {
- if (sum[i] > sum[k])
- k = i;
- }
- printf("%d %d %d\n", sum[k], s[a[k]], s[k]);
- }
- }
- return 0;
- }
能加个注释吗 ?比如那个max有什么用,程序里面不要它也可以啊
2009-08-15 @ 05:36
|本代码中max确实不是必要的。有两种办法可以获得最长连续子序列:一种是处理一个就判断,一种是全部处理好了以后再判断。max其实是前面一种,而本代码最终采用了后面一种思路。
2009-08-17 @ 19:08
|