HDU 1231 最大连续子序列

时间：2021-06-07 15:00:59

和前面两道题一样

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

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int a[maxn];

 struct Node

 {

     int w;

     int l, r;

 }node[maxn];

 int main(void)

 {

     #ifdef LOCAL

         freopen("1231in.txt", "r", stdin);

     #endif

     int n;

     while(scanf("%d", &n) && n)

     {

         int i;

         bool flag = true;

         for(i = ; i <= n; ++i)

         {

             scanf("%d", &a[i]);

             if(a[i] >= )    flag = false;

             node[i].w = a[i];

             node[i].l = node[i].r = i;

         }

         for(i = ; i <= n; ++i)

         {

             if(node[i-].w+a[i] >= node[i].w)

             {

                 node[i].w = node[i-].w + a[i];

                 node[i].l = node[i-].l;

             }

         }

         if(flag)

         {

             printf("0 %d %d\n", a[], a[n]);

             continue;

         }

         int ans = ;

         for(i = ; i <= n; ++i)

             if(node[i].w > node[ans].w)

                 ans = i;

         printf("%d %d %d\n", node[ans].w, a[node[ans].l], a[node[ans].r]);

     }

     return ;

 }

代码君

相关文章