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