HDU 1858 Max Partial Value I

求连续子序列的最大和

为毛简单的入门DP没有思路啊。。

学习下别人的解法，理解起来倒还是很容易的。

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int INF = -;

 struct Node

 {

     long long w;

     int l, r;

 }node[maxn];

 long long a[maxn];

 int main(void)

 {

     #ifdef LOCAL

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

     #endif

     int N;

     scanf("%d", &N);

     while(N--)

     {

         int n;

         scanf("%d", &n);

         int i;

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

         {

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

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

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

         }

         int ans = ;

         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(node[i].w > node[ans].w)

                 ans = i;

         }

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

     }

     return ;

 }

代码君