1049 最大子段和
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
N个整数组成的序列a[1],a[2],a[3],…,a[n]，
求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
Input
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
Output
输出最大子段和。
Input示例
6
-2
11
-4
13
-5
-2
Output示例
20思路是动态规划，时间复杂度 O(N)
对于前i个数来说，若前i-1个数的最长子段和为负，则前i个数的最长子段和为第i个数本身。（因为前面最大子段和为负，所以加上后反而更小）对于前i个数来说，若前i-1个数的最长子段和为正，则加上自己边界dp[0]=0，每一次更新最大值小心点，用long long，不然会溢出
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 long long ans[
100000],s[
100000];
5
6 inline
int read()
7 {
8 char ch=
getchar();
9 int k=
0,a=
1;
10 while (ch<
'0' || ch>
'9') {
11 if (ch==
'-') a=-
1;
12 ch=
getchar();
13 }
14 while (ch>=
'0'&&ch<=
'9') k=k*
10+(ch^
48),ch=
getchar();
15 return a*
k;
16 }
17
18 int main()
19 {
20 long long n,m=
1,k=
0;
21 m<<=
63;
22 scanf (
"%lld",&
n);
23 for (
int i=
1;i<=n;i++
)
24 {
25 scanf (
"%lld",&
s[i]);
26 if (s[i]>=
0) k=
1;
27 }
28 if (k==
0)
29 {
30 printf(
"0");
31 return 0;
32 }
33 for (
int i=
1;i<=n;i++
)
34 {
35 if (ans[i-
1]<=
0) ans[i]=
s[i];
36 else ans[i]=ans[i-
1]+
s[i];
37 m=
max(ans[i],m);
38 }
39 printf(
"%lld",m);
40 return 0;
41 }
View Code
转载于:https://www.cnblogs.com/rtyz/p/8323712.html
相关资源：JAVA上百实例源码以及开源项目
