🛩 Beginner-Friendly Guide 'Trionic Array II' - Problem 3640 (C++, Python, JavaScript)

Navigating complex array patterns often feels like climbing a mountain range. In this problem, we are looking for a very specific "up-down-up" shape within an array to find the maximum possible sum. This challenge tests your ability to identify structural patterns while optimizing for the best numerical outcome.

You're given:

• An array of integers called nums with a length .
• A requirement to find a "trionic" subarray, which follows a specific three-part sequence: strictly increasing, then strictly decreasing, then strictly increasing again.

Your goal:

• Identify all possible trionic subarrays that meet the index requirements .
• Calculate the sum of these subarrays and return the maximum sum found.

---

Intuition

The core of a trionic subarray is the "valley" formed by indices and . To satisfy the condition, we need a peak at and a trough at .

1. Identify the Core: We look for a segment where the numbers go up to a peak (), down to a trough (), and then back up.
2. The Pivot Points: The sequence between and (the decreasing part) is fixed once we identify a peak and a trough.
3. Greedy Expansion: To maximize the sum, we don't just take any and . We want the "prefix" before the peak and the "suffix" after the trough to be as large as possible. Since the values can be negative, we use a greedy approach to find the maximum prefix sum ending at and the maximum suffix sum starting after .

---

Walkthrough: Understanding the Examples

Example 2: `nums = [1, 4, 2, 7]`

• Step 1: We find an increasing sequence: . So, could be at index 1 (value 4).
• Step 2: We find a decreasing sequence: . So, could be at index 2 (value 2).
• Step 3: We find an increasing sequence: . So, could be at index 3 (value 7).
• Verification: . The segments are , , and .
• Sum: .

Example 1: `nums = [0, -2, -1, -3, 0, 2, -1]`

• The algorithm identifies the peak at index 2 (value -1) and the trough at index 3 (value -3).
• It then expands forward to include index 5 (value 2) because it continues the increasing trend.
• It expands backward to index 1 (value -2) because that provides the best sum for the initial increasing part.
• Sum: .

---

C++ Solution

class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        long long ans = -2e18; // Use a very small value for initialization
        while (i < n) {
            int l_bound = i;
            i += 1;
            // 1. Find the first increasing segment
            while (i < n && nums[i - 1] < nums[i]) {
                i += 1;
            }
            if (i == l_bound + 1) continue;

            int p = i - 1;
            long long current_sum = (long long)nums[p - 1] + nums[p];

            // 2. Find the strictly decreasing segment
            while (i < n && nums[i - 1] > nums[i]) {
                current_sum += nums[i];
                i += 1;
            }

            // Check if a valid trough 'q' exists
            if (i == p + 1 || i == n || nums[i - 1] == nums[i]) continue;

            int q = i - 1;
            // 3. Find the second increasing segment and its max prefix sum
            current_sum += nums[i];
            i += 1;
            long long max_suffix = 0, temp_suffix = 0;
            while (i < n && nums[i - 1] < nums[i]) {
                temp_suffix += nums[i];
                i += 1;
                max_suffix = max(max_suffix, temp_suffix);
            }
            current_sum += max_suffix;

            // 4. Look backward from p to find the max prefix sum for the first segment
            long long max_prefix = 0, temp_prefix = 0;
            for (int j = p - 2; j >= l_bound; j--) {
                temp_prefix += nums[j];
                max_prefix = max(max_prefix, temp_prefix);
            }
            current_sum += max_prefix;

            ans = max(ans, current_sum);
            i = q; // Reset pointer to trough to find overlapping patterns
        }
        return ans;
    }
};

Python Solution

class Solution:
    def maxSumTrionic(self, nums: list[int]) -> int:
        n = len(nums)
        i = 0
        ans = float('-inf')

        while i < n:
            l_bound = i
            i += 1
            # 1. Find the first increasing segment
            while i < n and nums[i - 1] < nums[i]:
                i += 1
            if i == l_bound + 1:
                continue

            p = i - 1
            current_sum = nums[p - 1] + nums[p]

            # 2. Find the strictly decreasing segment
            while i < n and nums[i - 1] > nums[i]:
                current_sum += nums[i]
                i += 1

            if i == p + 1 or i == n or nums[i - 1] == nums[i]:
                continue

            q = i - 1
            # 3. Find the second increasing segment
            current_sum += nums[i]
            i += 1
            max_suffix, temp_suffix = 0, 0
            while i < n and nums[i - 1] < nums[i]:
                temp_suffix += nums[i]
                i += 1
                max_suffix = max(max_suffix, temp_suffix)
            current_sum += max_suffix

            # 4. Find max prefix backward
            max_prefix, temp_prefix = 0, 0
            for j in range(p - 2, l_bound - 1, -1):
                temp_prefix += nums[j]
                max_prefix = max(max_prefix, temp_prefix)
            current_sum += max_prefix

            ans = max(ans, current_sum)
            i = q 

        return ans

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumTrionic = function(nums) {
    const n = nums.length;
    let i = 0;
    let ans = -Infinity;

    while (i < n) {
        let lBound = i;
        i += 1;
        // 1. Increasing
        while (i < n && nums[i - 1] < nums[i]) {
            i += 1;
        }
        if (i === lBound + 1) continue;

        let p = i - 1;
        let currentSum = BigInt(nums[p - 1]) + BigInt(nums[p]);

        // 2. Decreasing
        while (i < n && nums[i - 1] > nums[i]) {
            currentSum += BigInt(nums[i]);
            i += 1;
        }

        if (i === p + 1 || i === n || nums[i - 1] === nums[i]) continue;

        let q = i - 1;
        // 3. Second Increasing
        currentSum += BigInt(nums[i]);
        i += 1;
        let maxSuffix = 0n, tempSuffix = 0n;
        while (i < n && nums[i - 1] < nums[i]) {
            tempSuffix += BigInt(nums[i]);
            i += 1;
            if (tempSuffix > maxSuffix) maxSuffix = tempSuffix;
        }
        currentSum += maxSuffix;

        // 4. Backward Prefix
        let maxPrefix = 0n, tempPrefix = 0n;
        for (let j = p - 2; j >= lBound; j--) {
            tempPrefix += BigInt(nums[j]);
            if (tempPrefix > maxPrefix) maxPrefix = tempPrefix;
        }
        currentSum += maxPrefix;

        if (ans === -Infinity || currentSum > ans) {
            ans = currentSum;
        }
        i = q;
    }
    return Number(ans);
};

---

Key Takeaways

• Two-Pointer/Sliding Window: This problem uses a variation of the sliding window technique to find specific shapes (mountains and valleys) in linear time.
• Greedy Sub-problems: By using max(0, temp_sum), we effectively decide whether including extra elements helps us or hurts us. This is a mini-application of Kadane's logic within a structured pattern.
• Linear Complexity: Even though there is a nested loop to look backward, the main pointer i only moves forward through the array, ensuring time complexity.

Final Thoughts

Problems like "Trionic Array" are classic "pattern matching" questions often found in interviews for companies like Google or Amazon. They mimic real-world scenarios in signal processing or financial trend analysis, where a system needs to identify specific "bull" or "bear" market patterns before they complete. Mastering the ability to "walk" through an array while keeping track of multiple state changes is a vital skill for any software engineer.