最大子段和 题解

luogu P1115

题目简化

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

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

对于的数据，保证。
对于的数据，保证，。

算法：

Algorithm 1 40pts

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

#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，具体过程：

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

动态转移方程：

1	f[i] = max(f[i-1]+n[i],n[i])

时间复杂度自然是了。

代码：

#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分

当然，还有三分的解法。时间复杂度。

#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;
}

最大子段和 题解

题目简化

算法：

最大子段和题解