Let's decide on the two fruits that will be used. After that, we look for the longest continuous subsequence of those two fruits. This can be done by using the split
method (if your language supports it) or by maintaining a cnt
variable and traversing the list from the front. If the current element is one of the chosen types of fruits, add to cnt
. Otherwise, reset cnt
to . Find the maximum possible cnt
value.
Supposing there are types of fruits, there are ways to choose two of them, and each of the choices time. Total time complexity is .
#include <iostream>
#include <ranges>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> S(N);
for (int &s : S)
cin >> s;
int ans = 0;
for (int i = 1; i <= 9; i++)
for (int j = 1; j < i; j++)
{
auto v = S | views::transform([&](int x)
{ return x == i || x == j; });
for (auto w : views::split(v, false))
ans = max(ans, (int)distance(w.begin(), w.end()));
}
cout << ans << endl;
}
import re
def main():
input()
s=''.join(input().split())
ans = 0
for i in range(1, 10):
for j in range(1, i):
ans = max(ans, max(map(len, re.split(f'[^{i}{j}]', s))))
print(ans)
if __name__ == "__main__":
main()
use std::io::*;
use std::iter::FromIterator;
fn main() {
stdin().read_line(&mut String::new()).unwrap();
let mut s = String::new();
stdin().read_line(&mut s).unwrap();
let s = String::from_iter(s.chars().filter(|&x| !x.is_ascii_whitespace()));
let mut ans = 0;
for i in '1'..='9' {
for j in '1'..i {
ans = ans.max(
s.split(|x| x != i && x != j)
.map(|x| x.len())
.max()
.unwrap_or_default(),
);
}
}
println!("{}", ans);
}
Let's denote using , the rightmost point of the longest continuous sequence of two or less types of fruits starting from . That is, there are always two or less types of fruits in . Removing from the sequence, there are still two or less types of fruits in so is always larger than or equal to . Therefore, increases with $l.
Supposing was calculated, and since we know to be larger than or equal to , we can use a naive solution using a loop from increasing by each iteration looking for the maximum such that there are two or less types of fruits in . Since increases by in the loop, the number of iterations does not exceed .
Now we just need to find the types of fruits in fast. This can be done by maintaining a cnt
array of length in which we store the count of each type of fruit in the current range , and if we also store the number of types of fruits with more than fruit, this can be solved in time. Total complexity is .
Variable r
is used to maintain in the below code.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> S(N);
for (int &s : S)
cin >> s;
int ans = 0, r = 0, non_zero = 0;
vector<int> cnt(10);
for (int l = 0; l < N; l++)
{
while (r < N)
{
int nxt_non_zero = non_zero + (cnt[S[r]] == 0 ? 1 : 0);
if (nxt_non_zero <= 2)
{
cnt[S[r]]++;
r++;
non_zero = nxt_non_zero;
}
else
break;
}
ans = max(ans, r - l);
cnt[S[l]]--;
if (cnt[S[l]] == 0)
non_zero--;
}
cout << ans << endl;
}
def main():
N = int(input())
S = map(int, input().split())
ans = r = non_zero = 0
cnt = [0]*10
for l in range(N):
while r < N:
nxt_non_zero = non_zero + (1 if cnt[S[r]] == 0 else 0)
if nxt_non_zero <= 2:
cnt[S[r]] += 1
r += 1
non_zero = nxt_non_zero
else:
break
ans = max(ans, r - l)
cnt[S[l]] -= 1
if cnt[S[l]] == 0:
non_zero -= 1
print(ans)
if __name__ == "__main__":
main()
use std::io::*;
fn main() {
let n = read_vec()[0];
let s = read_vec();
let mut ans = 0;
let mut r = 0;
let mut non_zero = 0;
let mut cnt = [0; 10];
for l in 0..n {
while r < n {
let nxt_non_zero = non_zero + if cnt[s[r] as usize] == 0 { 1 } else { 0 };
if nxt_non_zero <= 2 {
cnt[s[r]] += 1;
r += 1;
non_zero = nxt_non_zero;
} else {
break;
}
}
ans = ans.max(r - l);
cnt[s[l]] -= 1;
if cnt[s[l]] == 0 {
non_zero -= 1;
}
}
println!("{}", ans);
}
fn read_vec() -> Vec<usize> {
let mut s = String::new();
stdin().read_line(&mut s).unwrap();
s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}