最大子段和 51Nod 1049

https://www.51nod.com/Challenge/Problem.html#problemId=1049

解题思路：

既然是求最大子段和，第一要求它是连续的一段数，二是最大。题目要求这里强调如果数据全为负数时就输出零，简化了问题。

申请一个数组dp[N]，如果 dp[i-1]+a[i]<0 的话，就跳过a[i]这一项。对于这里我们想象一下，dp数组中的值一定是大于等于零的，当dp[i]=dp[i-1]+a[i]<0时，将数存入dp是没有意义的。数据为负时就直接跳过它找下一个为正的数进行判断。如果dp[i-1]>0，然后遇到了一个正整数，那么dp[i-1]+a[i]的值应是大于等于a[i]的左邻域内包含a[i]的任意连续数的和。即，如果dp[i-1]+a[i]为正的话，那么就继续遍历，期望将其变为最大值。

代码：

 1 #include <bits/stdc++.h>
 2 
 3 #define N 100010
 4 
 5 using namespace std;
 6 
 7 typedef long long int ll;
 8 
 9 int main()
10 {
11     int n, i;
12     ll maxl;
13     ll dp[N]={0};  　　//之前这里弄错了orz,a[n]的范围是-10⁹~10⁹...用int会炸...
14     int a[N];
15     scanf("%d", &n);
16     for(i=1; i<=n; i++) scanf("%d", &a[i]);
17     maxl=0;
18     for(i=1; i<=n; i++){
19         if(dp[i-1]+a[i]>0) dp[i]=dp[i-1]+a[i];
20         maxl=max(dp[i], maxl);
21     }
22     printf("%lld\n", maxl);
23     return 0;
24 }

这道题还可以利用前缀和和贪心的思想去解。我们找前缀和中最小的值，尝试用当前的sum[i]-minl来更新ans。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <climits>
 7 
 8 #define N 100010
 9 
10 using namespace std;
11 
12 typedef long long int ll;
13 
14 int main()
15 {
16     int a[N];
17     int n, i;
18     ll sum[N]={0};
19     ll ans=0;
20     scanf("%d", &n);
21     for(i=1; i<=n; i++){
22         scanf("%d", &a[i]);
23         sum[i]=sum[i-1]+a[i];　　//求前缀和
24     }
25     ll minl;
26     minl=INT_MAX;
27     for(i=1; i<=n; i++){
28         minl=min(sum[i-1], minl);   //找最小值（可能是负数）
29         ans=max(ans, sum[i]-minl);  //符合条件就更新ans
30     }
31     if(ans<0) ans=0;
32     printf("%lld\n", ans);
33     return 0;
34 }