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。 简单DP 伪代码
start = 1
answerstart = asnwerend = 1
endmax = answer = a[1]
for end = 2 to n do
if endmax > 0 then
endmax += a[end]
else
endmax = a[end]
start = end
endif
if endmax > answer then
answer = endmax
answerstart = start
answerend = end
endif
endfor
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n;
4 const int maxn = 50005;
5 long long dp[maxn],a[maxn];
6 int main()
7 {
8 cin>>n;
9 for(int i=1;i<=n;i++)cin>>a[i];
10 int en=1,be=1;
11 dp[1]=1;
12 long long anbe=1,anen=1,enma=0,ans=1;
13 for(int i=1;i<=n;i++)
14 {
15 if(enma>=0)
16 {
17 enma+=a[i];
18 en=i;
19 }
20 else if(enma<0)
21 {
22 anbe=en;
23 enma=a[i];
24 }
25 if(enma>ans)
26 {
27 ans=enma;
28 anen=en;
29 anbe=be;
30 }
31 }
32 cout<<ans<<endl;
33 }
转载于:https://www.cnblogs.com/sortmin/p/7376809.html