3640. Trionic Array II

HardArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem 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.

In other words, a trionic subarray follows an "up-down-up" pattern: it first rises strictly, then falls strictly, and finally rises strictly again. Each of the three segments must contain at least two elements (i.e., the boundaries satisfy l < p < q < r), so the whole subarray needs a minimum of four elements with three distinct "turning points" at indices p and q.

Your task is to examine every possible trionic subarray, compute the sum of its elements, and return the largest such sum found across all valid candidates.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

The problem finds the maximum sum of a trionic subarray (up-down-up shape) by scanning monotonic runs and combining segments using DP state tracking.

Open in Flowchart

Intuition

The key observation is that a trionic subarray has a very specific shape: it goes up, then down, then up again. This shape is built entirely from "monotonic runs" — maximal stretches where the array is strictly increasing or strictly decreasing. So instead of checking every possible (l, p, q, r) combination, we can scan the array once and identify these runs as we go.

Think about how these runs connect. A strictly increasing run, followed by a strictly decreasing run, followed by another strictly increasing run, forms the core "up-down-up" skeleton. The natural strategy is to use a single pointer i that walks through the array and "consumes" each segment in turn:

First, consume a strictly increasing stretch (this gives us the rising part nums[l...p]).
Then, consume a strictly decreasing stretch (this gives us the falling part nums[p...q]).
Finally, consume another strictly increasing stretch (this gives us the second rising part nums[q...r]).

If any of these stretches fails to materialize (for example, a segment has only one element, or we hit equal adjacent values, or we run off the end of the array), the current candidate is invalid and we move on.

Once we lock onto a valid up-down-up core, we want to maximize the sum. Here's the clever part: the middle "down then up" structure (from p to just past q) is fixed for this candidate, but the two ends are flexible. We can extend the subarray:

Leftward from the start of the first increasing run — by including extra elements before p that keep increasing into our segment. Since these extra elements could be negative, we don't blindly take all of them; we track the maximum running sum as we extend left and only keep the best portion (or nothing, if extending hurts).
Rightward from the third increasing run — same idea. We extend through the trailing increasing elements and keep only the prefix that gives the maximum sum, using 0 if extending isn't beneficial.

This "take the best extension or none at all" logic is essentially a localized version of maximum subarray thinking applied to the two increasing tails.

The final reason this works in a single pass is the overlap trick: after processing one trionic subarray, the third increasing run can serve as the first increasing run of the next candidate. That's why the pointer is reset back to q rather than continuing forward — it lets adjacent up-down-up patterns chain together without re-scanning, keeping the whole algorithm linear.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

We use a grouped loop (also called a "segment scanning" technique): a single pointer i traverses the array, and within the loop we carve out the three required monotonic segments one after another. Let n be the length of nums, and initialize the answer ans = -inf.

Step 1 — Find the first strictly increasing segment.

We record the start l = i, then advance i while nums[i - 1] < nums[i]:

l = i
i += 1
while i < n and nums[i - 1] < nums[i]:
    i += 1
if i == l + 1:
    continue

If after this i == l + 1, the segment has only one element (no real increase), so this start cannot anchor a trionic subarray and we move on.

Step 2 — Find the strictly decreasing segment.

Pointer p = i - 1 marks the peak (end of the increasing part). We seed the running sum s with the last two values of the increasing run, nums[p - 1] + nums[p], then keep adding elements while the array strictly decreases:

p = i - 1
s = nums[p - 1] + nums[p]
while i < n and nums[i - 1] > nums[i]:
    s += nums[i]
    i += 1
if i == p + 1 or i == n or nums[i - 1] == nums[i]:
    continue

We discard this candidate if the decreasing segment is empty (i == p + 1), if we reached the array's end (i == n, leaving no room for the third segment), or if we stopped because of equal neighbors (nums[i - 1] == nums[i], which breaks strict monotonicity).

Step 3 — Find the second strictly increasing segment.

Pointer q = i - 1 marks the valley (end of the decreasing part). We add nums[i] (the first rising element after the valley) into s, then track the best prefix sum of the trailing increasing run using a running total t and its max mx:

q = i - 1
s += nums[i]
i += 1
mx = t = 0
while i < n and nums[i - 1] < nums[i]:
    t += nums[i]
    i += 1
    mx = max(mx, t)
s += mx

Here mx captures the maximum sum we can gain by extending rightward beyond the mandatory part of the third segment, and stays 0 if extending isn't beneficial. So far s covers the core range [p - 1, q + 1] plus the best right extension.

Step 4 — Extend leftward for the best left tail.

The increasing segment also lets us pull in elements before p - 1. We walk backward from p - 2 down to l, again keeping the maximum running sum:

mx = t = 0
for j in range(p - 2, l - 1, -1):
    t += nums[j]
    mx = max(mx, t)
s += mx

This adds the best leftward extension, again defaulting to 0 if no extension helps.

Step 5 — Update the answer and reset the pointer.

We update ans with the computed sum, then move i back to q:

ans = max(ans, s)
i = q

Resetting i = q is the key chaining trick: the third increasing run of the current trionic subarray can act as the first increasing run of the next candidate, so we re-enter the loop starting from the valley and continue without re-scanning.

Complexity.

Time complexity: O(n). Although the pointer is reset to q, each segment is processed a constant number of times overall, so the total work is linear.
Space complexity: O(1), since we only use a handful of pointers and running-sum variables.

Example Walkthrough

Let's trace through the solution approach with a small concrete example.

Input: nums = [1, 4, 2, 1, 3, 5], so n = 6, and we initialize ans = -inf, pointer i = 0.

This array has the shape: rises 1 → 4, falls 4 → 2 → 1, then rises 1 → 3 → 5 — a clean "up-down-up" pattern.

Step 1 — First strictly increasing segment.

Set l = i = 0, then advance i to 1.
Check nums[0] < nums[1] → 1 < 4 ✓, so i becomes 2.
Check nums[1] < nums[2] → 4 < 2 ✗, stop. Now i = 2.
Is i == l + 1? → 2 == 1? No. The increasing run [1, 4] is valid.

The peak is at index 1 (value 4).

Step 2 — Strictly decreasing segment.

Set p = i - 1 = 1 (the peak).
Seed s = nums[0] + nums[1] = 1 + 4 = 5 (last two of the rising run).
Check nums[1] > nums[2] → 4 > 2 ✓: s += 2 → s = 7, i = 3.
Check nums[2] > nums[3] → 2 > 1 ✓: s += 1 → s = 8, i = 4.
Check nums[3] > nums[4] → 1 > 3 ✗, stop. Now i = 4, s = 8.
Validity checks: i == p + 1? 4 == 2? No. i == n? 4 == 6? No. nums[3] == nums[4]? 1 == 3? No. Valid.

The valley is at index 3 (value 1). Core so far covers indices [0, 3] with s = 8.

Step 3 — Second strictly increasing segment.

Set q = i - 1 = 3 (the valley).
Add the first rising element after the valley: s += nums[4] = 3 → s = 11, then i = 5.
Initialize mx = t = 0 to track the best right extension.
Check nums[4] < nums[5] → 3 < 5 ✓: t += 5 → t = 5, i = 6, mx = max(0, 5) = 5.
Loop ends (i = 6 = n).
Add best right extension: s += mx = 5 → s = 16.

Now s = 16 covers the core [0, 4] plus the beneficial right tail (element 5).

Step 4 — Extend leftward.

Reset mx = t = 0. We walk from j = p - 2 = -1 down to l = 0.
Since p - 2 = -1 < l = 0, the range range(-1, -1, -1) is empty — there are no elements to the left of the mandatory start.
Add s += mx = 0 → s = 16 (no left extension available).

Step 5 — Update answer and reset pointer.

ans = max(-inf, 16) = 16.
Reset i = q = 3.

Re-entering the loop from i = 3, Step 1 starts a new increasing run at l = 3 (1 → 3 → 5), but no decreasing segment follows (we hit the end), so that candidate is discarded.

Result: The maximum trionic subarray sum is 16, corresponding to the full subarray [1, 4, 2, 1, 3, 5] (indeed 1+4+2+1+3+5 = 16).

This example shows how the single pointer carves out each segment, how the running-sum extensions default to 0 when they'd hurt (here the left side simply had nothing to add), and how s accumulates the core plus the best flexible tails.

Solution Implementation

1from typing import List
2from math import inf
3
4
5class Solution:
6    def maxSumTrionic(self, nums: List[int]) -> int:
7        n = len(nums)
8        i = 0
9        ans = -inf
10
11        while i < n:
12            # ---- Segment 1: strictly increasing run starting at `left` ----
13            left = i
14            i += 1
15            while i < n and nums[i - 1] < nums[i]:
16                i += 1
17            # No actual ascent: skip
18            if i == left + 1:
19                continue
20
21            # `peak` is the index of the peak (top of the first rise)
22            peak = i - 1
23            # Start the running sum with the last two elements of the rise:
24            # the element just before the peak and the peak itself.
25            total = nums[peak - 1] + nums[peak]
26
27            # ---- Segment 2: strictly decreasing run from the peak ----
28            while i < n and nums[i - 1] > nums[i]:
29                total += nums[i]
30                i += 1
31            # Need a real descent followed by a real ascent;
32            # also reject if we hit the end or a plateau (equal values).
33            if i == peak + 1 or i == n or nums[i - 1] == nums[i]:
34                continue
35
36            # `valley` is the index of the valley (bottom of the descent)
37            valley = i - 1
38            total += nums[i]
39            i += 1
40
41            # ---- Segment 3: strictly increasing run from the valley ----
42            # Extend the third (rising) part optimally: track the best
43            # running prefix sum so we only add a beneficial extension.
44            best, running = 0, 0
45            while i < n and nums[i - 1] < nums[i]:
46                running += nums[i]
47                i += 1
48                best = max(best, running)
49            total += best
50
51            # ---- Optionally extend the leading rise backwards ----
52            # Walk leftward from just before the (peak-1) element down to
53            # `left`, keeping the best running suffix sum to add.
54            best, running = 0, 0
55            for j in range(peak - 2, left - 1, -1):
56                running += nums[j]
57                best = max(best, running)
58            total += best
59
60            ans = max(ans, total)
61
62            # Reset to the valley so the next iteration can treat this
63            # valley as the start of a new (overlapping) trionic pattern.
64            i = valley
65
66        return ans
67

1class Solution {
2    public long maxSumTrionic(int[] nums) {
3        int n = nums.length;
4        int i = 0;
5        long ans = Long.MIN_VALUE;
6
7        while (i < n) {
8            // 'left' marks the start of a strictly increasing run
9            int left = i;
10            i++;
11            // Extend the first strictly increasing segment
12            while (i < n && nums[i - 1] < nums[i]) {
13                i++;
14            }
15            // If there was no actual increase (length 1), restart from here
16            if (i == left + 1) {
17                continue;
18            }
19
20            // 'peak' is the top of the increasing segment
21            int peak = i - 1;
22            // Sum must include at least the last edge of the increasing part:
23            // the peak and the element just before it
24            long sum = nums[peak - 1] + nums[peak];
25
26            // Extend the strictly decreasing segment
27            while (i < n && nums[i - 1] > nums[i]) {
28                sum += nums[i];
29                i++;
30            }
31            // No valid decrease, hit the end, or plateau -> invalid trionic shape
32            if (i == peak + 1 || i == n || nums[i - 1] == nums[i]) {
33                continue;
34            }
35
36            // 'valley' is the bottom of the decreasing segment
37            int valley = i - 1;
38            // Include the first step of the final increasing segment
39            sum += nums[i];
40            i++;
41
42            // Greedily extend the final increasing segment forward,
43            // taking the best (maximum) running sum of the extra elements
44            long maxExtend = 0;
45            long running = 0;
46            while (i < n && nums[i - 1] < nums[i]) {
47                running += nums[i];
48                i++;
49                maxExtend = Math.max(maxExtend, running);
50            }
51            sum += maxExtend;
52
53            // Greedily extend the first increasing segment backward,
54            // taking the best (maximum) running sum of the extra elements
55            maxExtend = 0;
56            running = 0;
57            for (int j = peak - 2; j >= left; j--) {
58                running += nums[j];
59                maxExtend = Math.max(maxExtend, running);
60            }
61            sum += maxExtend;
62
63            // Update the global best answer
64            ans = Math.max(ans, sum);
65
66            // Backtrack: the valley can serve as the start of a new
67            // increasing run for the next potential trionic subarray
68            i = valley;
69        }
70
71        return ans;
72    }
73}
74

1class Solution {
2public:
3    long long maxSumTrionic(vector<int>& nums) {
4        int n = nums.size();
5        int idx = 0;
6        long long ans = LLONG_MIN;
7
8        while (idx < n) {
9            // ---- Segment 1: strictly increasing run starting at 'start' ----
10            int start = idx;
11            idx += 1;
12            while (idx < n && nums[idx - 1] < nums[idx]) {
13                idx += 1;
14            }
15            // No actual increase happened (run of length 1) -> skip
16            if (idx == start + 1) {
17                continue;
18            }
19
20            // 'peak' is the index of the local maximum (end of increasing run)
21            int peak = idx - 1;
22            // Mandatory core sum: the last element of the increase + the peak
23            long long sum = nums[peak - 1] + nums[peak];
24
25            // ---- Segment 2: strictly decreasing run after the peak ----
26            while (idx < n && nums[idx - 1] > nums[idx]) {
27                sum += nums[idx];
28                idx += 1;
29            }
30            // Conditions that invalidate the pattern:
31            // - no decrease occurred (idx == peak + 1)
32            // - reached the end (no room for the third increasing segment)
33            // - a plateau (equal values) breaks strict monotonicity
34            if (idx == peak + 1 || idx == n || nums[idx - 1] == nums[idx]) {
35                continue;
36            }
37
38            // 'valley' is the index of the local minimum (end of decreasing run)
39            int valley = idx - 1;
40            // Add the first element of the third (increasing) segment
41            sum += nums[idx];
42            idx += 1;
43
44            // ---- Segment 3: optionally extend the final increasing run ----
45            // Track the best prefix sum of the extension (extension is optional,
46            // so the minimum contribution is 0).
47            long long best = 0, running = 0;
48            while (idx < n && nums[idx - 1] < nums[idx]) {
49                running += nums[idx];
50                idx += 1;
51                best = max(best, running);
52            }
53            sum += best;
54
55            // ---- Optionally extend the first increasing run backwards ----
56            // Walk back from just before the core start of the increase toward
57            // 'start', taking the best suffix-extension (optional, min 0).
58            best = 0;
59            running = 0;
60            for (int j = peak - 2; j >= start; j--) {
61                running += nums[j];
62                best = max(best, running);
63            }
64            sum += best;
65
66            // Update the global maximum
67            ans = max(ans, sum);
68
69            // Backtrack: the decreasing segment's valley may start a new
70            // increasing run, so resume scanning from 'valley'.
71            idx = valley;
72        }
73
74        return ans;
75    }
76};
77

1/**
2 * Finds the maximum sum of a "trionic" subarray.
3 * A trionic pattern consists of three strictly monotonic segments:
4 *   strictly increasing -> strictly decreasing -> strictly increasing.
5 */
6function maxSumTrionic(nums: number[]): number {
7    const length = nums.length;
8    let cursor = 0;
9    let answer = -Infinity;
10
11    while (cursor < length) {
12        // Mark the start of the first (increasing) segment.
13        const segmentStart = cursor;
14        cursor += 1;
15
16        // Advance through the strictly increasing run.
17        while (cursor < length && nums[cursor - 1] < nums[cursor]) {
18            cursor += 1;
19        }
20        // No actual increase happened; skip.
21        if (cursor === segmentStart + 1) continue;
22
23        // 'peakIndex' is the top of the first increasing segment.
24        const peakIndex = cursor - 1;
25
26        // Mandatory base sum: the last two elements of the increasing run.
27        let runningSum = nums[peakIndex - 1] + nums[peakIndex];
28
29        // Advance through the strictly decreasing run, accumulating its values.
30        while (cursor < length && nums[cursor - 1] > nums[cursor]) {
31            runningSum += nums[cursor];
32            cursor += 1;
33        }
34        // Invalid if: no decrease occurred, we hit the array end (no room for
35        // the final increasing segment), or the next pair is equal (not strict).
36        if (cursor === peakIndex + 1 || cursor === length || nums[cursor - 1] === nums[cursor]) {
37            continue;
38        }
39
40        // 'valleyIndex' is the bottom of the decreasing segment.
41        const valleyIndex = cursor - 1;
42
43        // Include the first element of the second increasing segment (mandatory).
44        runningSum += nums[cursor];
45        cursor += 1;
46
47        // Optionally extend into the rest of the second increasing run.
48        // Track the best prefix sum (only add if it improves the total).
49        let bestExtension = 0;
50        let prefixSum = 0;
51        while (cursor < length && nums[cursor - 1] < nums[cursor]) {
52            prefixSum += nums[cursor];
53            cursor += 1;
54            bestExtension = Math.max(bestExtension, prefixSum);
55        }
56        runningSum += bestExtension;
57
58        // Optionally extend backward into the earlier part of the first
59        // increasing run. Track the best suffix sum (only add if positive).
60        bestExtension = 0;
61        prefixSum = 0;
62        for (let backIndex = peakIndex - 2; backIndex >= segmentStart; backIndex--) {
63            prefixSum += nums[backIndex];
64            bestExtension = Math.max(bestExtension, prefixSum);
65        }
66        runningSum += bestExtension;
67
68        // Update the global maximum.
69        answer = Math.max(answer, runningSum);
70
71        // Resume scanning from the valley, since a new pattern could begin
72        // using the descent that ended at this valley as its own "up" start.
73        cursor = valleyIndex;
74    }
75
76    return answer;
77}
78

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

Although the code contains nested while loops and a for loop, each element of the array is processed a constant number of times overall. Let's break down the reasoning:

The outer while i < n loop drives the main traversal. Inside it, several inner loops advance the pointer i:
- The first inner loop (nums[i - 1] < nums[i]) scans the strictly increasing segment.
- The second inner loop (nums[i - 1] > nums[i]) scans the strictly decreasing segment.
- The third inner loop scans the next increasing segment.
After processing a valid "trionic" pattern, the line i = q resets the pointer back to the position q (the valley/turning point). This means part of the array may be revisited, but q is the start of the second increasing segment of the next candidate, so the backtracking is bounded.
The inner for j in range(p - 2, l - 1, -1) loop iterates over the first increasing segment in reverse. Its length is bounded by the size of the current increasing run, and across all iterations these runs sum to at most O(n).

Because the i = q reset only moves the pointer back to the boundary of the just-processed increasing run (not to the very beginning), the total number of pointer advances and the cumulative work of the reverse for loop remain linear. Thus the overall time complexity is O(n).

Space Complexity: O(1). The algorithm uses only a constant number of scalar variables (i, l, p, q, s, mx, t, ans, n, j) and does not allocate any auxiliary data structures that scale with the input size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Greedily extending the third increasing segment with a max-prefix-sum, but forgetting that the mandatory part of each segment must always be included

A very natural mistake when writing this solution is to treat all of the third increasing run as optional and let the "best prefix sum" logic decide how much to include — including the first rising step after the valley.

Look closely at the order of operations in Step 3:

valley = i - 1
total += nums[i]      # <-- the first rise after the valley is MANDATORY
i += 1

best, running = 0, 0
while i < n and nums[i - 1] < nums[i]:   # <-- only the REST is optional
    running += nums[i]
    i += 1
    best = max(best, running)
total += best

The element nums[valley + 1] (the first element of the third rise) is added unconditionally, before the max-prefix-sum loop begins. Only the elements beyond that mandatory rise are treated as an optional extension via best.

Why the naive version is wrong

A tempting but incorrect rewrite folds the first rise into the optional loop:

# WRONG: makes the first rising step optional too
best, running = 0, 0
while i < n and nums[i - 1] < nums[i]:
    running += nums[i]
    i += 1
    best = max(best, running)
total += best   # `best` could be 0, dropping the mandatory third segment!

Because best is seeded at 0, if every element of the third rise is negative (e.g. the run is -5, -3 after a valley of -7), best stays 0. The code would then discard the entire third segment, producing a subarray that is not even trionic — it would only have an up-down shape. The structural requirement q < r (third segment has at least two elements) would be silently violated.

Concretely, for nums = [3, 1, -5, -3]:

Increasing: 3 is not a real rise on its own — but consider [1, 3, ... ] style inputs. With negative valleys/rises, the naive code can report a sum that corresponds to a non-trionic shape, or even leave ans = -inf incorrectly when a valid (but negative-sum) trionic subarray exists.

The mandatory total += nums[i] guarantees the third segment always contributes its required minimum two elements (the valley nums[valley] already accounted for plus nums[valley+1]), keeping the candidate structurally valid even when its sum is negative.

Same trap on the left side

The symmetric pitfall exists in Step 4. The left extension walks from peak - 2 downward:

for j in range(peak - 2, left - 1, -1):
    ...

It starts at peak - 2, not peak - 1, because nums[peak - 1] and nums[peak] were already included unconditionally in Step 2 (total = nums[peak - 1] + nums[peak]). A common off-by-one bug is to start the loop at peak - 1 and double-count nums[peak - 1], or to start at peak and double-count the peak itself.

Solution

Keep the mandatory minimum of each segment separate from its optional extension:

First rise: always include nums[peak - 1] + nums[peak] (the two-element minimum).
Descent: always include every strictly-decreasing element (it is not optional — it is forced by the structure).
Second rise: always include the first step nums[valley + 1]; treat only the elements after it as an optional max-prefix extension.
Left extension: start the backward scan at peak - 2 to avoid re-adding nums[peak - 1].

A useful defensive check is to verify with an all-negative trionic input, e.g. nums = [-1, -3, -2, -4, -3] (or similar up-down-up shapes of negative numbers), where the correct answer must still be a finite negative sum — not 0 and not -inf. If your code returns 0, you have made some part of a mandatory segment optional; if it returns -inf, you have over-pruned a valid candidate.

# Correct: mandatory parts added directly, only true extensions are max-pruned
total = nums[peak - 1] + nums[peak]   # mandatory rise minimum
# ... add all descent elements (mandatory) ...
total += nums[valley + 1]             # mandatory first step of third rise
total += best_right_extension         # optional, defaults to 0
total += best_left_extension          # optional, defaults to 0

This separation is what guarantees every reported sum corresponds to a genuinely trionic (up-down-up) subarray while still maximizing the total via the optional tails.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: