P1115 最大字段和 题解

题目简化

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

输入 $n$ 和序列 $a$ ，输出一行一个整数表示答案。

• 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。

算法：

Algorithm 1 40pts

三层循环枚举左右端点以及区间的和，找出最大字段和，时间复杂度 $O(n^3)$。

#include<bits/stdc++.h>
using namespace std;
const int maxN = 2e5+10;
int a[maxN];
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i]; 
    }
    int maxx = -1e9;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            int sum = 0;
            for(int i=l;i<=r;i++){
                sum += a[i];
            }
            maxx = max(maxx,sum);
        }
    }
    cout << maxx << endl;
    return 0;
}

期望得分40分。

Algorithm 2 100pts

dp，具体过程：

• 将第一个数成为一个答案序列。

• 如果下一个数加上上一个答案序列得到的结果比这个数$\red大$，那么该数也属于这个答案序列。

• 如果下一个数加上上一个答案序列得到的结果比这个数$\red小$，那么该数单独成为一个答案序列。

• 如果下一个数加上上一个答案序列得到的结果与这个数$\red{相等}$，那么该数也属于这个答案序列。(因为加和没加没有区别，但加了还有可能继续变大,毕竟是最大子段和。)

动态转移方程：

时间复杂度自然是 $O(n)$ 了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int M = -1e6;
int n;
int a[N],f[N]; // a为数列，f[i]为到i为止它所在答案序列的元素和。
int maxf = M;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> a[i];
    for(int i=1;i<=n;i++){
        f[i] = max(a[i],f[i-1]+a[i]);
        if(f[i] > maxf) maxf = f[i];
    }
    cout << maxf << endl;
    return 0;
}

期望得分100分。

Algorithm 3 100分

我们自然可以想到把上面的答案数组进行优化，因为b[i]只需要b[i-1]来计算，所以可以优化成一个变量。（a就不用说了吧）

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n; 
    cin >> n;
    int ans = -1e9;
    int a,b;
    for(int i=1; i<=n; i++) {
        cin >> a;
        if(i == 1) b = a;
        else b = max(a,a+b);
        ans = max(ans,b);
    }
    cout << ans << endl;
    return 0;
}

Algorithm 4 100分

当然，还有三分的解法。时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
int n,arr[200200];
const int minn = -1e9;
int rec(int l,int r) { // 分治函数
	if (l == r) {    // l=r时，直接返回该位置的值
		return arr[l];
	}
	int mid = ( l + r ) >> 1;
	int sum = 0 , ret1 = minn , ret2 = minn; //ret1为[l..mid]区间内包含mid的最大子段和，ret2为[mid+1..r]区间内包含(mid+1)的最大子段和
	for( int i = mid ; i >= l ; i-- ) {
		sum += arr[i];
		ret1 = max( ret1 , sum );
	}  //求出[i..mid]区间最大值
	sum = 0;
	for( int i = mid+1 ; i <= r ; i++ ) {
		sum += arr[i];
		ret2 = max( ret2 , sum );
	}  //求出[mid+1..r]区间最大值
	return max( max( rec( l , mid ) , rec( mid + 1 , r ) ) , ret1 + ret2 );   //返回可能一 可能二 可能三 中的最大值
}
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i++ ) {
		cin >> arr[i];
	}
	cout << rec(1,n) << endl;
	return 0;
}