407. Jump Game IX

From each starting index, run a DFS following the legal jump rules and record the maximum value reached. Repeat for every starting index. Quadratic, but it directly mirrors the problem statement.

Approach

For each i:

1. DFS from i over the implicit graph: edge i → j allowed if (j > i and nums[j] < nums[i]) or (j < i and nums[j] > nums[i]).
2. Track the maximum value seen during the traversal.
3. ans[i] = that maximum.

Complexity

• Time: O(n²) — each DFS may walk the whole array.
• Space: O(n) for the visited set.

import java.util.*;

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int start = 0; start < n; start++) {
            Set<Integer> seen = new HashSet<>();
            seen.add(start);
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            int best = nums[start];
            while (!stack.isEmpty()) {
                int i = stack.pop();
                best = Math.max(best, nums[i]);
                for (int j = 0; j < n; j++) {
                    if (seen.contains(j)) continue;
                    if ((j > i && nums[j] < nums[i]) || (j < i && nums[j] > nums[i])) {
                        seen.add(j);
                        stack.push(j);
                    }
                }
            }
            ans[start] = best;
        }
        return ans;
    }
}

Notice that within certain segments of the array, every index can reach every other index — and across segment boundaries, no jump is possible. The boundary lives wherever the prefix max up to here is ≤ the suffix min after here. Once we find these segments, every index in a segment shares the same answer: the segment's maximum.

Why segment boundaries exist

Consider a position i such that every value in nums[0..i] is ≤ every value in nums[i+1..n-1]. Then:

• A forward jump from [0..i] to [i+1..n-1] would need nums[j] < nums[k] with j ≤ i, k > j — but that's impossible if every left value is ≤ every right value (we'd need a strict <, but our condition allows equality at the boundary which still blocks).
• A backward jump from [i+1..n-1] to [0..i] would need nums[j] > nums[k] with j > k — again impossible by the same reasoning.

So the array is partitioned into segments where no jump crosses a boundary. Within a single segment, the values "interleave" enough that every index can reach the segment's maximum (by some chain of legal jumps).

Detecting boundaries

Compute prefix_max[i] = max of nums[0..i] and suffix_min[i] = min of nums[i..n-1]. Position i ends a segment iff i == n - 1 or prefix_max[i] <= suffix_min[i+1].

Steps

1. Build prefix_max and suffix_min arrays in two linear passes.
2. Walk i from 0 to n - 1. Maintain a seg_start index and a running seg_max:
   • Update seg_max = max(seg_max, nums[i]).
   • If i == n - 1 or suffix_min[i + 1] >= prefix_max[i]:
     • This closes a segment. Set ans[j] = seg_max for j in [seg_start, i].
     • Reset seg_start = i + 1, seg_max = 0.
3. Return ans.

Walk-through

nums = [2, 1, 3]. Expected: [2, 2, 3].

prefix_max = [2, 2, 3], suffix_min = [1, 1, 3].

Final: ans = [2, 2, 3]. ✓

Another, nums = [2, 3, 1]. Expected: [3, 3, 3].

prefix_max = [2, 3, 3], suffix_min = [1, 1, 1].

Result: [3, 3, 3]. ✓

Edge cases

• Strictly increasing nums: every index is its own segment (no jump possible). Each ans[i] = nums[i].
• Strictly decreasing nums: all in one segment; everyone reaches the max.
• Constant nums: equality blocks all jumps (need strict inequality), so every index is alone — ans[i] = nums[i].

Complexity

• Time: O(n) — three linear passes.
• Space: O(n) for the prefix/suffix arrays and the answer.