首页 > 代码库 > HDU 1858 Max Partial Value I

HDU 1858 Max Partial Value I

2024-07-13 19:04:08   221人阅读

求连续子序列的最大和

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

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

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 1000000 + 10; 9 const int INF = -10000000;10 11 struct Node12 {13     long long w;14     int l, r;15 }node[maxn];16 17 long long a[maxn];18 19 int main(void)20 {21     #ifdef LOCAL22         freopen("1858in.txt", "r", stdin);23     #endif24 25     int N;26     scanf("%d", &N);27     while(N--)28     {29         int n;30         scanf("%d", &n);31         int i;32         for(i = 1; i <= n; ++i)33         {34             scanf("%I64d", &a[i]);35             node[i].w = a[i];36             node[i].l = node[i].r = i;37         }38 39         int ans = 1;40         for(i = 2; i <= n; ++i)41         {42             if(node[i-1].w+a[i] >= node[i].w)43             {44                 node[i].w = node[i-1].w + a[i];45                 node[i].l = node[i-1].l;46             }47             if(node[i].w > node[ans].w)48                 ans = i;49         }50 51         printf("%I64d %d %d\n", node[ans].w, node[ans].l, node[ans].r);52     }53     return 0;54 }
代码君


联系
我们