最大连续和（子串）

青旅半醒 2024-04-17 05:22 98阅读 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;
    }

![20190821233552711.png][]

前面的数字是答案，后面的 t 是计算加法的运行次数。

[20190821233552711.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/d8d04344bd6d449582210e5bc2a58d6c.png