#cs/cp #TODO You are given an integer array `nums` of length $n$, with elements $n_0,\dots,n_{n-1}$. A subarray is arithmetic if the difference between every pair of consecutive elements is constant. You may replace at most one element in `nums` with any integer. Return the maximum possible length of an arithmetic subarray. # Solution Precompute two arrays: - $left[i]$: the length of the longest arithmetic subarray ending at $i$. - $right[i]$: the length of the longest arithmetic subarray starting at $i$. Compute `left` with a forward scan and `right` with a backward scan. Initialize the answer with the longest run already present, then consider each index $i$ as the element to replace: 1. Replacing $n_i$ can extend the run ending at $i-1$ or the run starting at $i+1$ by one. 2. To join both runs, the replacement must satisfy $ n_i-n_{i-1}=n_{i+1}-n_i, $ so $n_{i+1}-n_{i-1}$ must be even and the shared difference must be $ d=\frac{n_{i+1}-n_{i-1}}{2}. $ Extend left and right only while their existing differences equal $d$. Each index is processed a constant number of times, so the algorithm takes $O(N)$ time and $O(N)$ space.