PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given an array A, find the length of its longest subarray whose sum is even.
EXPLANATION:
The constraints are small enough that you can simply bruteforce all subarrays and check in \mathcal{O}(N^2) (or even \mathcal{O}(N^3)).
However, it is also possible to solve the problem in linear time with a bit of thought.
Notice that the only thing that determines whether a subarray’s sum is even or odd, is the number of odd integers it contains.
If it has an odd number of odd integers, the sum is odd; if it has an even number of odd integers, the sum is even.
So, if A itself contains an even number of odd integers, the entire array A has even sum, and the answer is N.
Otherwise, we have to exclude at least one odd number.
It’s easy to see that since we want to maximize length, it’s best to exclude either the first odd number or the last one.
So, find the positions of the first and last odd number - say indices x and y.
The answer is then the maximum of N-x and y-1 (either exclude x and everything before it, or exclude y and everything after it).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
a[i] %= 2
if sum(a)%2 == 0:
print(n)
continue
remove = n
for i in range(n):
if a[i] == 1:
remove = min(remove, i+1)
break
for i in reversed(range(n)):
if a[i] == 1:
remove = min(remove, n-i)
break
print(n - remove)
