You are given an array of integers nums of length n. The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3. You need to divide nums into 3 disjoint contiguous subarrays. Return

minimumCost.js

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

    // We must split into 3 subarrays, so n must be at least 3.
    // If n == 3, there's no choice: each element starts a subarray.
    if (n === 3) {
        return nums[0] + nums[1] + nums[2];
    }

    // -------------------------------
    // Step 1: Build suffix-min array
    // suffixMin[i] = minimum value in nums[i ... n-1]
    // -------------------------------
    const suffixMin = new Array(n);
    suffixMin[n - 1] = nums[n - 1];

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

    // -------------------------------
    // Step 2: Try all possible starts for subarray #2
    // i ranges from 1 to n-2
    // For each i, the best j is the smallest nums[j] for j >= i+1
    // which is suffixMin[i+1]
    // -------------------------------
    let bestPair = Infinity;

    for (let i = 1; i <= n - 2; i++) {
        const costSecond = nums[i];
        const costThird = suffixMin[i + 1]; // best possible j > i
        bestPair = Math.min(bestPair, costSecond + costThird);
    }

    // -------------------------------
    // Step 3: Add the fixed cost of the first subarray
    // -------------------------------
    return nums[0] + bestPair;
};