AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 3801. 最佳连续子数组    原题链接    简单

作者: 作者的头像   ywt51 ,  2023-05-26 14:10:39 ,  所有人可见 ,  阅读 34


0


算法1:双指针-扫描连续段() $O(n)$
//最大值就是最大平均值, 找最大值连续出现的长度
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int a[N], n, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int mx = -1, res = 0;
        for (int i = 0; i < n; ++ i) {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        } 
        //1. 变量记录的方式
        int len = 0;
        for (int i = 0; i < n; ++ i) {
            if (a[i] == mx) len++; //连续相等就累加
            else len = 0; //最大值中断了,清零,从新计数
            res = max(res, len); 
        }

        //2. 双指针扫描的方式
        // for (int i = 0; i < n; ++ i) 
        //     if (a[i] == mx) { 
        //         int j = i;
        //         while (a[j] == mx && j < n) j++;
        //         res = max(res, j-i);
        //         i = j;
        //     }
        printf("%d\n", res);
    }
    return 0;
}
算法2:变量维护最大值及其连续长度() $O(n)$
#include <bits/stdc++.h>
using namespace std;

int n, T, x;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int res = 1, mx = -1, len = 0; //len记录当前最大值连续长度 mx最大值 res最大长度
        while (n--) {
            scanf("%d,", &x);
            if (x > mx) mx = x, res = len = 1; //值最大优先,值最大的前提下 长度多
            else if (x == mx) len++, res = max(res, len);
            else len = 0;
        }
        printf("%d\n", res);
    }
    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息