Longest Arithmetic Subarray with One Optional Replacement

### Problem You are given an integer array `nums`. You may replace at most one element with any integer, then select a nonempty contiguous subarray. A subarray is arithmetic when every difference between consecutive elements is the same. Return the greatest possible length of such a subarray after the optional replacement. The replacement may be negative, zero, or outside the original input-value bounds. Elements cannot be skipped: this is a subarray problem, not an arbitrary subsequence problem. ```cpp class Solution { public: int longestArithmetic(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text Input: nums = [4,7,10,50,16,19] Output: 6 Explanation: Replace 50 with 13. The entire array becomes [4,7,10,13,16,19], with common difference 3. Its length six is the largest possible. ``` **Example 2:** ```text Input: nums = [40,2,7,12] Output: 4 Explanation: Replace the first value with -3. The array [-3,2,7,12] is arithmetic with common difference 5. A replacement is allowed outside the positive input bounds. ``` ### Constraints - `4 <= nums.length <= 100000`. - `1 <= nums[i] <= 100000` for the original input. - At most one replacement is permitted, using any integer. ### Clarifying Questions - Must the chosen positions be consecutive? Yes. - Must a replacement be made? No; an existing arithmetic subarray may be used. - Can the common difference be zero or negative? Yes. - Must the replacement respect the original value limits? No; those limits describe only the given input. - Is the selected subarray or replacement returned? No; return only the maximum length. ### What a Strong Answer Covers - Contiguity, constant differences, and the global limit of one optional replacement. - The full integer replacement domain and the unchanged original-input constraints. - An attainable maximum and a completeness proof, including no-change and endpoint cases. - Equality, negative differences, integer feasibility, and full-size numeric and resource bounds. ### Follow-up Questions - What extra fields would be needed to return a witness interval and its optional replacement? - What would need specification if replacements were limited to a supplied finite set? ```hint Join only runs with the required common difference Precompute lengths of unchanged arithmetic runs ending and starting at each index. A replacement can extend one side. To join both sides, its neighbors must differ by an even number, fixing the common difference. Use a whole neighboring run only if its adjacent difference agrees with that fixed difference; otherwise only its nearest single element can participate. ```