完美序列

使用前缀和记录到当前的大于k比小于等于k的数量，找前面到当前的完美序列，只需满足后面的前缀和大于前面的前缀和，这样这段区间就是完美序列。从前往后遍历的一定符合到当前的最长，找的break就可以。时间复杂度为O(n^2)。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
//#define mod 998244353
#define mod 1000000007
#define ll long long
using namespace std;
const int N=1e6+5;
const double eps=1e-8;
int n,m,k;
void solve(){
    cin>>n>>k;
    vector<int>vc(n+5,0);
    int sum=0;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(x>k){
            sum++;
        }
        else{
            sum--;
        }
        vc[i+1]=sum;
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(vc[i]>vc[j-1]){
                maxx=max(maxx,i-j+1);
                break;
            }
        }
    }
    cout<<maxx<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(10);
    //int t;
    //cin>>t;
    //while(t--){
        solve();
    //}
    return 0;
}

import java.util.*;

public class Main {
    // 完美序列-前缀和！
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n];
        int[] pre = new int[n+1];
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            arr[i] = num > k ? 1 : -1;
            pre[i+1] = pre[i] + arr[i];
        }
        int max = 0;
        for (int i = 1; i < n+1; i++) {
            for (int j = 0; j < i; j++) {
                if (pre[i]-pre[j] > 0) {
                    max = Math.max(max, i-j);
                }
            }
        }
        System.out.println(max);
    }
}

 #include <iostream>

using namespace std;

const int N = 10100;
int n, k;
int g[N];
int res = 0;
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i ++) cin >> g[i];
    if(g[0] > k) g[0] = 1;
    else g[0] = -1;
    for(int i = 1; i < n; i ++)
    {
        if(g[i] > k ) g[i] = g[i - 1] + 1;
        else g[i] = g[i - 1] - 1;
    }
    for(int i = 0; i < n; i ++)
        if(g[i] > 0) res = i + 1;
    for(int i = 1; i + res < n; i ++)
    {
        for(int j = i + res; j < n; j ++)
            if(g[j] > g[i]) res = j - i;
    }
    cout << res;
}

时间复杂度貌似最优就是 吗？python 提交的话记得选 jit 编译器 pypy ，要不然有一些测试样例会被卡时间。

n, k = list(map(int, input().split(" ")))
nums = list(map(int, input().split(" ")))
pre = [0]
for i in range(len(nums)):
    pre.append(pre[-1] + 1) if nums[i] > k else pre.append(pre[-1])

result = float("-inf")
for i in range(len(nums)):
    for j in range(i, len(nums)):
        gt_k = pre[j + 1] - pre[i]
        if gt_k > (j - i + 1 - gt_k):
            result = max(result, j - i + 1)
print(result)