You are given an integer array nums of length n. A trionic subarray is a contiguous subarray nums[l...r] (with 0 <= l < r < n) for which there exist indices l < p < q < r such that: nums[l...p] is strictly increasing, nums[p...q] is strictly decrea

maxSumTrionic.js

/**
 * @param {number[]} nums
 * @return {number}
 *
 * This solution uses top‑down DP with memoization.
 * We track 4 phases (k = 0..3) of a trionic subarray:
 *
 *   0 → before starting the first increasing phase
 *   1 → strictly increasing
 *   2 → strictly decreasing
 *   3 → final strictly increasing (valid trionic)
 *
 * At each index i, we decide whether to:
 *   - skip nums[i] (only allowed in phase 0)
 *   - take nums[i] and transition to the next phase if allowed
 *
 * The recursion returns the maximum sum achievable from index i
 * while currently in phase k.
 */
var maxSumTrionic = function(nums) {
    const n = nums.length;
    const NEG = -1e18; // represents an impossible state

    // dp[i][k] = best result starting at index i in phase k
    const dp = Array.from({ length: n }, () => Array(4).fill(null));

    function solve(i, k) {
        // If we've consumed the array:
        // Only phase 3 is valid (completed trionic)
        if (i === n) {
            return k === 3 ? 0 : NEG;
        }

        if (dp[i][k] !== null) return dp[i][k];

        let take = NEG;     // take nums[i] and continue pattern
        let notTake = NEG;  // skip nums[i] (only allowed in phase 0)

        // Phase 0 allows skipping elements until we find a valid start
        if (k === 0) {
            notTake = solve(i + 1, 0);
        }

        // Try to take nums[i] and move to the next index
        if (i + 1 < n) {
            let next = NEG;

            // Phase 0 → Phase 1 (start increasing)
            if (k === 0 && nums[i + 1] > nums[i]) {
                next = solve(i + 1, 1);

            // Phase 1 transitions
            } else if (k === 1) {
                if (nums[i + 1] > nums[i]) {
                    next = solve(i + 1, 1); // continue increasing
                } else if (nums[i + 1] < nums[i]) {
                    next = solve(i + 1, 2); // switch to decreasing
                }

            // Phase 2 transitions
            } else if (k === 2) {
                if (nums[i + 1] < nums[i]) {
                    next = solve(i + 1, 2); // continue decreasing
                } else if (nums[i + 1] > nums[i]) {
                    next = solve(i + 1, 3); // switch to final increase
                }

            // Phase 3 transitions (final increasing)
            } else if (k === 3 && nums[i + 1] > nums[i]) {
                next = solve(i + 1, 3);
            }

            // If the transition was valid, include nums[i]
            if (next !== NEG) {
                take = nums[i] + next;
            }
        }

        // Special case:
        // In phase 3, we may end the trionic subarray at i
        if (k === 3) {
            take = Math.max(take, nums[i]);
        }

        // Best of taking or skipping
        return dp[i][k] = Math.max(take, notTake);
    }

    return solve(0, 0);
};