最大连续和（子串）-蒲公英云

最大连续和（子串）

青旅半醒 2024-04-17 05:22 131阅读 0赞

用了4种方法实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
const ll mod=1e9+7;
int a[10000],b[10000],c[10000];
int n = 1000,t1 = 0,t2 = 0,t3 = 0,t4 = 0;
void init(){
    for(int i = 1;i <= n;i++){
        a[i] = i;
    }
}
//O(n^3)
int baoli(){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            int sum = 0;
            for(int k = i;k <= j;k++) {sum += a[k];t1++;}
            ans = max(ans,sum);
        }
    }
    return ans;
}
//O(n^2)
int qzh(){
    int ans = 0;
    b[1] = a[1];
    for(int i = 2;i <= n;i++) {b[i] = b[i-1]+a[i];t2++;}
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            ans = max(ans,b[j]-b[i-1]);
            t2++;
        }
    }
    return ans;
}
//O(n)
int qzh_plus(){
    int ans = 0;
    b[1] = a[1];c[1] = a[1];
    for(int i = 2;i <= n;i++) {b[i] = b[i-1]+a[i];t4++;}
    for(int i = 2;i <= n;i++) {c[i] = b[c[i-1]]>b[i]?i:c[i-1];t4++;}
    for(int i = 1;i <= n;i++){
        ans = max(ans,b[i]-b[c[i]-1]);
    }
    return ans;
}
//O(nlogn)
int fenzi(int x,int y){
    if(y == x){
        return a[x];
    }
    int mid = (x+y)/2;t3++;
    int ans = max(fenzi(x,mid),fenzi(mid+1,y));
    int le = 0,rt = 0,temp = 0;
    for(int i = mid;i >= x;i--) {le = max(le,temp+=a[i]);t3++;}
    temp = 0;
    for(int i = mid+1;i <= y;i++) {rt = max(rt,temp+=a[i]);t3++;}
    ans = max(ans,le+rt);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    cout<<"baoli = "<<baoli();
    cout<<"  t1 = "<<t1<<endl;
    cout<<"qzh   = "<<qzh();
    cout<<"  t2 = "<<t2<<endl;
    cout<<"fenzi = "<<fenzi(1,n);
    cout<<"  t3 = "<<t3<<endl;
    cout<<"plus  = "<<qzh_plus();
    cout<<"  t4 = "<<t4<<endl;
    return 0;
}