Longest Arithmetic Subarray After One Change
MediumAsked in:Amazon•Stage:Online Assessment
Problem Statement
Given an array of n integers, you may change at most one element to any integer value. After the change, find the maximum possible length of a contiguous subarray that forms an arithmetic progression. Return that maximum length.
Input Format
The first line contains an integer n (the size of the array). The second line contains n space‑separated integers a1,a2,…,an.
Output Format
Print a single integer — the maximum length of a contiguous arithmetic subarray achievable after changing at most one element.
Constraints
- 1 <= n <= 10^5
- -10^9 <= a[i] <= 10^9
- Time complexity should be O(n)