P1115 最大子段和

链接：https://www.luogu.com.cn/problem/P1115

方法一：0分代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, a[210000];
 4 int ans=-(1<<30);
 5 int sum(int l, int r){
 6     int ret=0;
 7     for(int i=l; i<=r; i++)ret+=a[i];
 8     return ret;
 9 }
10 int main()
11 {
12     cin>>n;
13     for(int i=1; i<=n; i++)cin>>a[i]; 
14     for(int i=1; i<=n; i++)
15         for(int j=i; j<=n; j++)
16             ans=max(ans,sum(i, j));
17     cout<<ans;    
18     return 0;    
19 }

方法二：使用前缀和，但无优化（40分代码）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, a[210000], presum[210000];
 4 int ans=-(1<<30);//答案求最大值，初始化为最小值 
 5 int main()
 6 {
 7     cin>>n;
 8     for(int i=1; i<=n; i++)cin>>a[i];
 9     for(int i=1; i<=n; i++)presum[i]=presum[i-1]+a[i];//求前缀和 
10     for(int i=1; i<=n; i++)
11         for(int j=i; j<=n; j++)
12             ans=max(ans,presum[j]-presum[i-1]);
13     cout<<ans;    
14     return 0;    
15 }

方法三：前缀和加优化（100分）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, a[210000], psum[210000];
 4 int minl;//用于存放左端点最小的前缀和值 
 5 int ans=-(1<<30);
 6 int main()
 7 {
 8     cin>>n;
 9     for(int i=1; i<=n; i++){
10         cin>>a[i];
11         psum[i]=psum[i-1]+a[i];//输入同时求出前缀和 
12     }
13     minl=0;
14     for(int i=1; i<=n; i++){
15         ans=max(ans, psum[i]-minl);//求最大的区间和 
16         minl=min(minl, psum[i]);//依次枚举最小左端点 
17     }
18     cout<<ans;
19     return 0;
20 }

方法四：递推法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int k;
 4 int a[200005];
 5 int dp[200005];//当前位置之前的最大字段和 
 6 int main()
 7 {
 8     scanf("%d",&k);
 9     for(int i=0; i<k; i++)
10         scanf("%d",&a[i]);
11     dp[0]=a[0];
12     int ans=dp[0];
13     for(int i=1; i<k; i++)
14     {
15         dp[i]=max(a[i], dp[i-1]+a[i]);//dp[i]与a[i]有关 
16         ans=max(ans, dp[i]);
17     }
18     //(int i=0; i<k; i++)printf("%d ",dp[i]);
19     //printf("
");
20     printf("%d",ans);
21     return 0;
22 }