首页 > 代码库 > HDU 1231 最大连续子序列

HDU 1231 最大连续子序列

2024-07-13 19:24:52   225人阅读

和前面两道题一样

不过这题要求输出子序列首尾的元素的值，而且如果所有元素都小于0的话，规定子序列的和为0，并输出整个序列的首尾元素。

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 10000 + 10; 8 int a[maxn]; 9 10 struct Node11 {12     int w;13     int l, r;14 }node[maxn];15 16 int main(void)17 {18     #ifdef LOCAL19         freopen("1231in.txt", "r", stdin);20     #endif21 22     int n;23     while(scanf("%d", &n) && n)24     {25         int i;26         bool flag = true;27         for(i = 1; i <= n; ++i)28         {29             scanf("%d", &a[i]);30             if(a[i] >= 0)    flag = false;31             node[i].w = a[i];32             node[i].l = node[i].r = i;33         }34 35         for(i = 2; i <= n; ++i)36         {37             if(node[i-1].w+a[i] >= node[i].w)38             {39                 node[i].w = node[i-1].w + a[i];40                 node[i].l = node[i-1].l;41             }42         }43 44         if(flag)45         {46             printf("0 %d %d\n", a[1], a[n]);47             continue;48         }49 50         int ans = 1;51         for(i = 2; i <= n; ++i)52             if(node[i].w > node[ans].w)53                 ans = i;54         printf("%d %d %d\n", node[ans].w, a[node[ans].l], a[node[ans].r]);55     }56     return 0;57 }
代码君


联系
我们