Trionic Array II

hard array dynamic programming subarray

Problem

A trionic subarray nums[l..r] (with 0 ≤ l < r < n) has split points l < p < q < r where nums[l..p] is strictly increasing, nums[p..q] is strictly decreasing, and nums[q..r] is strictly increasing — an up-down-up shape. Return the maximum sum of any trionic subarray. At least one is guaranteed to exist.

Inputnums = [0, -2, -1, -3, 0, 2, -1]

Output-4

Take l=1, p=2, q=3, r=5: [-2,-1] up, [-1,-3] down, [-3,0,2] up. Sum = (-2)+(-1)+(-3)+0+2 = -4.

nums (comma-separated, length ≥ 4)

def maxSumTrionic(nums):
    NEG = float("-inf")
    # dpk[i] = best sum of a run ending at i after finishing phase k
    # phase1 = increasing, phase2 = decreasing, phase3 = increasing
    dp0, dp1, dp2, dp3 = nums[0], NEG, NEG, NEG
    best = NEG
    for i in range(1, len(nums)):
        n0, n1, n2, n3 = nums[i], NEG, NEG, NEG   # dp0 always restarts at i
        if nums[i] > nums[i - 1]:                  # an increasing step
            n1 = max(dp0, dp1) + nums[i]           # open or extend phase1
            n3 = max(dp2, dp3) + nums[i]           # open or extend phase3
        elif nums[i] < nums[i - 1]:                # a decreasing step
            n2 = max(dp1, dp2) + nums[i]           # open or extend phase2
        dp0, dp1, dp2, dp3 = n0, n1, n2, n3
        best = max(best, dp3)                      # dp3 = a full trionic run
    return best

function maxSumTrionic(nums) {
  const NEG = -Infinity;
  // dpk = best sum of a run ending at i after finishing phase k
  // phase1 = increasing, phase2 = decreasing, phase3 = increasing
  let dp0 = nums[0], dp1 = NEG, dp2 = NEG, dp3 = NEG;
  let best = NEG;
  for (let i = 1; i < nums.length; i++) {
    let n0 = nums[i], n1 = NEG, n2 = NEG, n3 = NEG; // dp0 restarts at i
    if (nums[i] > nums[i - 1]) {                    // an increasing step
      n1 = Math.max(dp0, dp1) + nums[i];            // open or extend phase1
      n3 = Math.max(dp2, dp3) + nums[i];            // open or extend phase3
    } else if (nums[i] < nums[i - 1]) {             // a decreasing step
      n2 = Math.max(dp1, dp2) + nums[i];            // open or extend phase2
    }
    dp0 = n0; dp1 = n1; dp2 = n2; dp3 = n3;
    best = Math.max(best, dp3);                     // dp3 = a full trionic run
  }
  return best;
}

long maxSumTrionic(int[] nums) {
    final long NEG = Long.MIN_VALUE / 4;
    // dpk = best sum of a run ending at i after finishing phase k
    // phase1 = increasing, phase2 = decreasing, phase3 = increasing
    long dp0 = nums[0], dp1 = NEG, dp2 = NEG, dp3 = NEG;
    long best = NEG;
    for (int i = 1; i < nums.length; i++) {
        long n0 = nums[i], n1 = NEG, n2 = NEG, n3 = NEG; // dp0 restarts
        if (nums[i] > nums[i - 1]) {                     // increasing step
            n1 = Math.max(dp0, dp1) + nums[i];           // open/extend phase1
            n3 = Math.max(dp2, dp3) + nums[i];           // open/extend phase3
        } else if (nums[i] < nums[i - 1]) {              // decreasing step
            n2 = Math.max(dp1, dp2) + nums[i];           // open/extend phase2
        }
        dp0 = n0; dp1 = n1; dp2 = n2; dp3 = n3;
        best = Math.max(best, dp3);                      // full trionic run
    }
    return best;
}

long long maxSumTrionic(vector<int>& nums) {
    const long long NEG = LLONG_MIN / 4;
    // dpk = best sum of a run ending at i after finishing phase k
    // phase1 = increasing, phase2 = decreasing, phase3 = increasing
    long long dp0 = nums[0], dp1 = NEG, dp2 = NEG, dp3 = NEG;
    long long best = NEG;
    for (int i = 1; i < (int)nums.size(); i++) {
        long long n0 = nums[i], n1 = NEG, n2 = NEG, n3 = NEG; // dp0 restarts
        if (nums[i] > nums[i - 1]) {                          // increasing step
            n1 = max(dp0, dp1) + nums[i];                     // open/extend phase1
            n3 = max(dp2, dp3) + nums[i];                     // open/extend phase3
        } else if (nums[i] < nums[i - 1]) {                   // decreasing step
            n2 = max(dp1, dp2) + nums[i];                     // open/extend phase2
        }
        dp0 = n0; dp1 = n1; dp2 = n2; dp3 = n3;
        best = max(best, dp3);                                // full trionic run
    }
    return best;
}

Explanation

A trionic subarray has a fixed up → down → up shape. Rather than guessing the four split points l < p < q < r, we run a single left-to-right dynamic-programming sweep and track, for the run ending at each index, which phase it has finished.

We keep four rolling values. dp0 is just the current element as a potential left endpoint l. dp1 is the best sum of a run ending here that is in the first increasing stretch (so it has cleared phase 1). dp2 is the best run that has switched into the decreasing middle. dp3 is the best run that has switched back into the final increasing stretch — a complete trionic subarray.

At index i the comparison with nums[i-1] decides which transitions are legal. On an increasing step we may continue phase 1 or open it from dp0 (n1 = max(dp0, dp1) + nums[i]), and we may continue phase 3 or open it from the decreasing phase (n3 = max(dp2, dp3) + nums[i]). On a decreasing step we continue or open the middle (n2 = max(dp1, dp2) + nums[i]). An equal step breaks all strict runs, so only dp0 survives by restarting at i.

Each phase requires at least two elements with a strict comparison, and because dp1 can only feed dp2 which can only feed dp3, any value that lands in dp3 has genuinely gone up, then down, then up. We update best = max(best, dp3) after every index, and the answer is the largest dp3 seen.

Example: nums = [0,-2,-1,-3,0,2,-1]. The window [-2,-1,-3,0,2] rises, falls, then rises and lands in dp3 with sum -4, which is the best full trionic run.

Time: O(n) Space: O(1)