Longest Subarray with Constant Difference
Given an array A of N integers, find the length of the longest subarray such that the difference between any two adjacent elements in the subarray is constant. A subarray is a contiguous part of the array. For example, in [5, 7, 9, 11], the differences are 7-5=2, 9-7=2, 11-9=2. This subarray has a constant difference of 2.
Input
The first line contains an integer N, the size of the array. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer, the length of the longest subarray with a constant difference between adjacent elements.
Constraints
1 <= N <= 200000 -10^9 <= A_i <= 10^9
Example 1
7 1 3 5 7 9 11 13
7
The entire array forms a subarray with a constant difference of 2.
Example 2
8 1 2 3 5 7 9 10 11
4
The longest subarrays are [1, 2, 3] (diff 1) and [5, 7, 9] (diff 2) and [10, 11] (diff 1). The longest is length 3.
Hints
Similar problems
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Longest Sorted SubsegmentMedium
- Longest Subarray with Limited DifferenceMedium
- Minimum Operations to Make Array SortedMedium
- Max Consecutive SumMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
More topics: Arrays problems, Two Pointers problems, Greedy problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
7 1 3 5 7 9 11 13
8 1 2 3 5 7 9 10 11