Longest Subarray with Alternating Parity
Given an array of N integers, find the length of the longest contiguous subarray such that the parity (even or odd) of adjacent elements alternates. For example, in the array [1, 2, 3, 4, 5], adjacent elements have alternating parity (odd, even, odd, even, odd). In contrast, in [1, 2, 4, 5], the subarray [2, 4] does not have alternating parity because both 2 and 4 are even.
Input
The first line contains a single integer N. The second line contains N integers, the elements of the array.
Output
Print a single integer, the length of the longest contiguous subarray with alternating parity.
Constraints
1 <= N <= 200000. Each element of the array is between 1 and 10^9.
Example 1
5 1 2 3 4 5
5
All adjacent elements have alternating parity, so the whole array is the longest subarray.
Example 2
7 1 2 4 5 6 7 9
4
The longest alternating subarray is [1, 2] (length 2), [4, 5] (length 2), [5, 6] (length 2), [6, 7] (length 2), [7, 9] (length 2), and also [4, 5, 6] is not alternating. [1,2], [4,5], [5,6], [6,7] and [7,9]. Longest is [4,5] or [5,6] or [6,7] length 2. Correct is [1,2] length 2. Oh wait [1,2], [4,5]
Hints
Similar problems
- Count Subarrays with Distinct ElementsMedium
- Optimal Training ScheduleMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Subarray with Sum at Most KMedium
- Longest Subarray with Increasing SumMedium
- Longest Subarray with Bounded DifferenceMedium
More topics: Two Pointers problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 5
7 1 2 4 5 6 7 9