关于用max，min函数超时的情况—算法小Tips

今天在做这道题的时候，有了一点对一些题max函数min函数就会超时的思考，不是每道题都这样，但也可以是个做题小tips；

题目连接：登录—专业IT笔试面试备考平台_牛客网

题目很简单，用个前缀和暴力一下就行，但不是最优解，会超时

我最开始的代码如下：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<string,string>
const int N = 1e6;
int a[N],sum[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=7;
        sum[i]=a[i]+sum[i-1];
        
    }
    int ans=-1,flag=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if((sum[j]-sum[i-1])%7==0){
                ans=max(j-i+1,ans);
                flag=1;
            }
        }
    }
    if(flag==1)cout<<ans;
    else cout<<-1;
    
}

在这个代码中，我在每个能被7整除的区间都进行了一次max判断，本来就是O（n2）的复杂度，可能有很多被7整除的情况，都要进入 if((sum[j]-sum[i-1])%7==0){
                ans=max(j-i+1,ans);
                flag=1;
            }

中进行max比较，从而加大了处理次数，这道题也是超时了。

修改代码如下：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<string,string>
const int N = 1e6;
int a[N],sum[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=7;
        sum[i]=sum[i]+a[i-1];
        
    }
    int maxx=-1,flag=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){

            int t=j-i+1;

            if(t>=maxx){
            
            if((a[j]-a[i-1])%7==0){
                maxx=t;
                flag=1;
                }

            }
        }
    }
    if(flag==1)cout<<maxx;
    else cout<<-1;
    return 0;
}

很明显，我把没有比之前最大值大的数直接pass掉，不进入是否被7整除的区间判断，从而减小了处理次数。

综上所述：尽量不要偷懒，暴力用max或者min函数进行判断，会增加很多没必要的处理次数，有时候就是因为这个会卡着你过不去，所以可以直接定义一个变量进行与当前值比大小的判断，节省了用max函数或者min函数。