时间复杂度O(n)的算法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

//−100000≤ Ai ≤100000

typedef long long ll;

int n;

ll arr[maxn];

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&arr[i]);

    }

    int r=2;

    ll maxsum=LONG_LONG_MIN;//权值和最大的层的权值和

    int maxdep=0;//权值和最大的层

    ll sum=0;

    int dep=1;

    for(int i=1;i<=n;i++){

        if(i==r){

            if(sum>maxsum){

                maxsum=sum;

                maxdep=dep;

            }

            sum=0;

            dep++;

            r<<=1;

        }

        sum+=arr[i];

    }

    if(sum>maxsum){

        maxsum=sum;

        maxdep=dep;

    }

    printf("%d",maxdep);

    system("pause");

    return 0;

}