Longest Divisible Subarray with One Optional Sign Flip

# Longest Divisible Subarray with One Optional Sign Flip You are given an integer array `nums` and a positive integer `k`. A nonempty contiguous subarray is valid if its sum is divisible by `k` either as it is or after negating one element inside that subarray. Negating a value `x` changes it to `-x`. Return the longest valid subarray's length. If no valid nonempty subarray exists, return `0`. ### Function `int longestSubarray(vector<int>& nums, int k)` ### Example 1 **Input:** `nums = [-2, 1, 2], k = 5` **Output:** `3` **Explanation:** The whole array sums to `1`. Negate its first element, changing `-2` to `2`; the sum becomes `2 + 1 + 2 = 5`, which is divisible by `5`. ### Example 2 **Input:** `nums = [1, 2, 4], k = 8` **Output:** `0` **Explanation:** No singleton is divisible by `8`, with or without negation. The two length-`2` sums are `3` and `6`, and their possible sums after one negation are `1`, `-1`, `2` and `-2`. The whole array sums to `7`, with possible one-negation sums `5`, `3` and `-1`. None is divisible by `8`. ### Constraints - `1 <= nums.length <= 1000` - `-100000 <= nums[i] <= 100000` - `1 <= k <= 100000` ### Clarifications - At most one element may be negated for the chosen subarray; doing nothing is allowed. - The negated element must belong to that subarray. - Zero and negative sums may be divisible by `k`; in particular, zero is divisible by every permitted `k`. - Validity is an existence check. You need not return a modified array, a subarray or the negated index. ### What a Strong Answer Covers - Considering nonempty contiguous ranges and allowing the no-negation case. - Accounting for the full effect of negating a positive or negative value within the chosen range. - Handling zero sums, negative values and cases with no valid subarray.