[题解]P1115 最大子段和

最大子段和问题

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

分治法($O(n\log n)$)

设区间$[l,r]$中点为$mid$，最大子段和为$[i,j]$，$[i,j]$位置有以下情形:

• $l\le i\le j\le mid$；(完全在左半区)
• $l\le i\le mid\le j\le r$；(横跨两区)
• $mid\le i\le j\le r$(完全在右半区)

vector<int>v;
int Find(int l,int r){//处理横跨左右两个区间
    int m=l+r>>1;//在中间分别向两侧扫描
    int suml=0,ansl=v[m];//suml:临时变量,ansl:左区间最大和
    int sumr=0,ansr=v[m+1];//sumr:临时变量,ansr:右区间最大和
    for(int i=m;i>=l;i--){
        suml+=v[i];
        ansl=max(ansl,suml);
    }
    for(int i=m+1;i<=r;i++){
        sumr+=v[i];
        ansr=max(sumr,ansr);
    }
    return ansl+ansr;//加和即为整段区间最大和
}
int Max(int l,int r){
    if(l==r) return v[l];
    int m=l+r>>1;
    //分治法,将区间不断细分,直到把所有数拆成横跨区间情形
    int ml=Max(l,m);
    int mr=Max(m+1,r);
    int mlr=Find(l,r);//处理横跨左右两个区间
    int ans=max({ml,mr,mlr});
    return ans;
}

贪心(O($n$))

负数对于答案的贡献非常恶劣，因此在此子段和<0时，抛弃此子段，从此子段的下一个位置重新选取子段，会使答案更优

int n,ans=-INFINITY;
vector<int>v;
void solve(){
	int sum=0;
	for(auto i:v){
		sum+=i;
		ans=max(sum,ans);
		if(sum<0) sum=0;
	}
	cout<<ans<<endl;
}

DP($O(n)$)

思路1：从前向后转移

• 状态定义：
  • 集合：$dp[]$：$1-i$区间内最大子段和
  • 属性：$max$
• 状态计算：
  • 子段连续,子段和继承自元素i-1
  • 子段不连续,子段和从第i个元素开始重新计算

转移方程式：$dp[i]=max(dp[i-1]+v[i],v[i])$

extern int n;
extern vector<int>v,dp;
void Max(){
	dp[0]=v[0];
    for(int i=1;i<v.size();i++)
        dp[i]=max(dp[i-1]+v[i],v[i]);
    cout<<*max_element(dp.begin(),dp.end())<<endl;
}

思路2：从后向前转移

转移方程式：$dp[i]=max(dp[i+1]+v[i],v[i])$

extern int n;
extern vector<int>v,dp;
void Max(){
	dp[n-1]=v[n-1];
    for(int i=n;i>=0;i--)
        dp[i]=max(dp[i+1]+v[i],v[i]);
    cout<<*max_element(dp.begin(),dp.end())<<endl;
}