3640. Trionic Array II

Description

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 decreasing,
• nums[q...r] is strictly increasing.

Return the maximum sum of any trionic subarray in nums.

 

Example 1:

Input: nums = [0,-2,-1,-3,0,2,-1]

Output: -4

Explanation:

Pick l = 1, p = 2, q = 3, r = 5:

• nums[l...p] = nums[1...2] = [-2, -1] is strictly increasing (-2 < -1).
• nums[p...q] = nums[2...3] = [-1, -3] is strictly decreasing (-1 > -3)
• nums[q...r] = nums[3...5] = [-3, 0, 2] is strictly increasing (-3 < 0 < 2).
• Sum = (-2) + (-1) + (-3) + 0 + 2 = -4.

Example 2:

Input: nums = [1,4,2,7]

Output: 14

Explanation:

Pick l = 0, p = 1, q = 2, r = 3:

• nums[l...p] = nums[0...1] = [1, 4] is strictly increasing (1 < 4).
• nums[p...q] = nums[1...2] = [4, 2] is strictly decreasing (4 > 2).
• nums[q...r] = nums[2...3] = [2, 7] is strictly increasing (2 < 7).
• Sum = 1 + 4 + 2 + 7 = 14.

 

Constraints:

• 4 <= n = nums.length <= 105
• -109 <= nums[i] <= 109
• It is guaranteed that at least one trionic subarray exists.

 

Solutions

Solution: Simulation

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

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSumTrionic = function (nums) {
  const n = nums.length;
  let index = 0;
  let result = Number.MIN_SAFE_INTEGER;

  while (index < n) {
    let l = index + 1;
    let sum = 0;

    while (l < n && nums[l - 1] < nums[l]) {
      l += 1;
    }

    const p = l - 1;

    if (p === index) {
      index += 1;
      continue;
    }

    sum += nums[p] + nums[p - 1];

    while (l < n && nums[l - 1] > nums[l]) {
      sum += nums[l];
      l += 1;
    }

    const q = l - 1;

    if (q === p || q === n - 1 || (l < n && nums[l] === nums[q])) {
      index = q + 1;
      continue;
    }

    sum += nums[q + 1];

    let segmentSum = 0;
    let maxSum = 0;

    for (let k = q + 2; k < n; k++) {
      if (nums[k] <= nums[k - 1]) break;

      segmentSum += nums[k];
      maxSum = Math.max(segmentSum, maxSum);
    }

    sum += maxSum;
    segmentSum = 0;
    maxSum = 0;

    for (let k = p - 2; k >= index; k--) {
      segmentSum += nums[k];
      maxSum = Math.max(segmentSum, maxSum);
    }

    sum += maxSum;
    result = Math.max(sum, result);
    index = q;
  }

  return result;
};