Maximum Value Reachable Under Directional Jumps

### Problem You are given an integer array `nums`. Starting at index `i`, a jump to a different index `j` is allowed under exactly these rules: - If `j > i`, then `nums[j]` must be strictly smaller than `nums[i]`. - If `j < i`, then `nums[j]` must be strictly larger than `nums[i]`. For every starting index, return the largest array **value** reachable by any sequence of allowed jumps. The starting position itself is reachable without making a jump. Return an array `ans` of the same length, where `ans[i]` is that maximum value for start `i`. ```cpp class Solution { public: vector<int> maxValue(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text Input: nums = [4,1,3,6,5] Output: [4,4,4,6,6] Explanation: Index 0 can reach indices 1 and 2, and either can jump back to index 0. Indices 3 and 4 can reach each other. No allowed sequence connects these two groups, so their reachable maximum values are 4 and 6. ``` **Example 2:** ```text Input: nums = [2,2,1,4,4] Output: [2,2,2,4,4] Explanation: Each of the first two positions can jump to index 2, and index 2 can jump back to either of them. The equal-valued entries at indices 3 and 4 cannot jump to each other, and neither can reach a larger value elsewhere. Equal values alone do not allow a jump. ``` ### Constraints - `1 <= nums.length <= 100000`. - `1 <= nums[i] <= 1000000000`. ### Clarifying Questions - Must a jump go to an adjacent index? No; any other index satisfying the rule is permitted. - Can equal values satisfy either jump rule? No. Both comparisons are strict. - Is only one jump allowed? No. Use any finite sequence of allowed jumps. - Does the answer report a value or an index? A value. - Are repeated values allowed in the input? Yes; uniqueness is not promised. ### What a Strong Answer Covers - The different forward and backward conditions, including strictness. - Reachability through multiple jumps and inclusion of the starting value. - Correct answers for every original index, including duplicate values and a single element. - A complete reachability argument and resource bounds suitable for the full input size. ### Follow-up Questions - What should every answer be when all input values are equal? - Can a route with several jumps reach a value that no single jump from its start can reach? ```hint Find where reachability separates For two indices in increasing index order, a larger value on the left permits travel in both directions between them. Consider whether a boundary has any such pair crossing it; prefix maxima and suffix minima can test that condition. ```