You are given an integer array nums. From any index i, you can jump to another index j under the following rules: Jump to index j where j > i is allowed only if nums[j] < nums[i]. Jump to index j where j < i is allowed only if nums[j] > nums[i]. Fo

maxValue.js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var maxValue = function(nums) {
    const n = nums.length;
    const pref = Array(n);
    const suff = Array(n);

    // prefix max
    pref[0] = nums[0];
    for (let i = 1; i < n; i++) {
        pref[i] = Math.max(pref[i-1], nums[i]);
    }

    // suffix min
    suff[n-1] = nums[n-1];
    for (let i = n-2; i >= 0; i--) {
        suff[i] = Math.min(suff[i+1], nums[i]);
    }

    const ans = Array(n);
    let start = 0;

    for (let i = 0; i < n - 1; i++) {
        // cut between i and i+1
        if (pref[i] <= suff[i+1]) {
            const segmentMax = pref[i];
            for (let j = start; j <= i; j++) {
                ans[j] = segmentMax;
            }
            start = i + 1;
        }
    }

    // last segment
    const segmentMax = pref[n-1];
    for (let j = start; j < n; j++) {
        ans[j] = segmentMax;
    }

    return ans;
};