poj2479 Maximum sum(简单dp,连续子段和最大)

思路来源

https://blog.csdn.net/zwj1452267376/article/details/51457411

题意

即求两个不相交的连续子段，使二者的和最大。

题解

如果仅一个子段的话，考虑尺取或者dp均可。

尺取的思想是，维护sum为当前和，舍弃小于0的子段，即若sum<0则将sum置0。

dp的思想类似，将dp[i]定义为以i为结尾的最大子段和的值，

后续通过更新左端点，更新为0到i这一段的最大子段和的值。

若dp[i-1]<0则只取当前a[i]，

否则dp[i]=dp[i-1]+a[i]，递推式即dp[i]=max(dp[i-1]+a[i],a[i]);

两个子段的话，考虑枚举划分点i，分为[0,i)和[i,n-1]两个部分，

l[]数组为增序遍历的最大子段和，r[]数组为降序遍历的最大子段和。

注意下标。

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int t,n,a[50005],l[50005],r[50005],ans;
void init()
{
	mem(l,0);
   	mem(r,0);
   	ans=-INF;
}
int main()
{ 
   sci(t);
   while(t--)
   {
   	init();
   	sci(n);
   	rep(i,0,n-1)
	{
	  sci(a[i]);
	  l[i+1]=max(l[i]+a[i],a[i]);//l下标,1-n,即[0,i)
    }
    rep(i,2,n)l[i]=max(l[i],l[i-1]);//将左端点更新至0 
    per(i,n-1,0)r[i]=max(r[i+1]+a[i],a[i]);//r下标,(n-1)-0,即[i,n-1] 
    per(i,n-2,0)r[i]=max(r[i],r[i+1]);//将右端点更新至(n-1) 
    rep(i,1,n-1)ans=max(ans,l[i]+r[i]);//1-n与(n-1)-0的交集只有1-(n-1)
	printf("%d\n",ans); 
   }
   return 0;
}