LeetCode 3640 - Trionic Array II

We are given an integer array nums, and we must find the maximum possible sum of a contiguous subarray that follows a very specific shape: 1. It first increases strictly. 2. Then decreases strictly. 3. Then increases strictly again. More formally, for a subarray nums[l...

leetcodehardarraydynamic-programming

LeetCode Problem 3640

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

We are given an integer array nums, and we must find the maximum possible sum of a contiguous subarray that follows a very specific shape:

  1. It first increases strictly.
  2. Then decreases strictly.
  3. Then increases strictly again.

More formally, for a subarray nums[l...r], there must 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.

The subarray must be contiguous, and all three phases must exist. A purely increasing array, a purely decreasing array, or an increasing-decreasing array without the final increasing segment is not valid.

The goal is to maximize the sum of all elements inside such a trionic subarray.

The constraints are important:

  • n can be as large as 100,000.
  • Values can be as small as -10^9 and as large as 10^9.

A brute force solution that checks every subarray is completely infeasible. Even an O(n²) solution would be too slow for n = 100,000.

Several edge cases are worth noting:

  • Values may be negative, so the maximum trionic subarray is not necessarily long.
  • The optimal answer may itself be negative.
  • Equal adjacent values cannot belong to any strictly increasing or strictly decreasing segment.
  • Every phase must contain at least one comparison, which means each segment has length at least two.
  • The problem guarantees that at least one valid trionic subarray exists.

Approaches

Brute Force

A straightforward approach is to enumerate every possible subarray nums[l...r].

For each subarray, we would try all possible choices of p and q and verify whether:

  • nums[l...p] is strictly increasing,
  • nums[p...q] is strictly decreasing,
  • nums[q...r] is strictly increasing.

If the subarray is valid, compute its sum and update the answer.

This approach is correct because it explicitly checks every valid trionic subarray. However, it is far too slow. There are O(n²) subarrays, and validating each one can require additional scanning, leading to O(n³) or worse complexity.

With n = 100,000, this is completely impractical.

Key Insight

The trionic shape is really a sequence of three monotonic phases:

  • Increasing
  • Decreasing
  • Increasing

Instead of explicitly choosing boundaries (l, p, q, r), we can process the array from left to right and maintain the best sum for each phase.

Define three dynamic programming states:

  • dp1: best strictly increasing subarray ending at the current index.
  • dp2: best increasing-then-decreasing subarray ending at the current index.
  • dp3: best increasing-decreasing-increasing subarray ending at the current index.

Each state only depends on the previous position.

Whenever we encounter:

  • an increasing edge (nums[i-1] < nums[i]), we can extend increasing states,
  • a decreasing edge (nums[i-1] > nums[i]), we can extend decreasing states.

This allows us to build valid trionic subarrays incrementally in a single pass.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) or worse O(1) Enumerates subarrays and validates shape explicitly
Optimal DP O(n) O(n) Tracks best sums for the three required phases

Algorithm Walkthrough

State Definitions

Let:

  • dp1[i] = maximum sum of a strictly increasing subarray ending at index i.
  • dp2[i] = maximum sum of an increasing-then-decreasing subarray ending at index i.
  • dp3[i] = maximum sum of an increasing-decreasing-increasing subarray ending at index i.

Each state represents a valid structure whose last element is nums[i].

Transition Logic

1. Build increasing segments (dp1)

If:

nums[i-1] < nums[i]

then we can:

  • start a new increasing segment of length 2:
nums[i-1] + nums[i]
  • or extend an existing increasing segment:
dp1[i-1] + nums[i]

Take the maximum of those options.

2. Build increasing-decreasing segments (dp2)

If:

nums[i-1] > nums[i]

then we can:

  • start the decreasing phase from a completed increasing segment:
dp1[i-1] + nums[i]
  • or extend an existing decreasing phase:
dp2[i-1] + nums[i]

Take the maximum.

3. Build trionic segments (dp3)

If:

nums[i-1] < nums[i]

then we can:

  • start the final increasing phase from a completed dp2:
dp2[i-1] + nums[i]
  • or extend an existing final increasing phase:
dp3[i-1] + nums[i]

Take the maximum.

4. Track the Answer

Every valid trionic subarray corresponds to some dp3[i].

Therefore:

answer = max(dp3[i])

over all indices.

Why it works

The key invariant is that each DP state represents the maximum sum of a valid structure ending at the current position.

  • dp1 contains only strictly increasing segments.
  • dp2 contains only increasing-then-decreasing segments.
  • dp3 contains only increasing-decreasing-increasing segments.

The transitions exactly mirror the only legal way to move between phases:

Increasing -> Increasing-Decreasing -> Trionic

Since every valid trionic subarray must be constructed through these phase transitions, and each state always stores the maximum possible sum for that structure ending at the current position, the maximum value appearing in dp3 is the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        NEG_INF = -10**30

        dp1 = [NEG_INF] * n
        dp2 = [NEG_INF] * n
        dp3 = [NEG_INF] * n

        answer = NEG_INF

        for i in range(1, n):
            if nums[i - 1] < nums[i]:
                dp1[i] = max(
                    nums[i - 1] + nums[i],
                    dp1[i - 1] + nums[i]
                )

                dp3[i] = max(
                    dp2[i - 1] + nums[i],
                    dp3[i - 1] + nums[i]
                )

            if nums[i - 1] > nums[i]:
                dp2[i] = max(
                    dp1[i - 1] + nums[i],
                    dp2[i - 1] + nums[i]
                )

            answer = max(answer, dp3[i])

        return answer

The implementation directly follows the DP formulation.

The dp1 array stores the best strictly increasing segment ending at each index. Whenever the current pair forms an increasing edge, we either start a new increasing segment of length two or extend a previous one.

The dp2 array represents the first two phases of the trionic structure. It can only be updated when the current edge is decreasing. We either begin the decreasing phase from a completed increasing segment or continue an existing decreasing phase.

The dp3 array represents a complete trionic structure. It can only be updated when the current edge is increasing. We either start the final increasing phase from a completed dp2 structure or continue extending an existing trionic subarray.

The answer is the maximum value ever stored in dp3.

Go Solution

func maxSumTrionic(nums []int) int64 {
	n := len(nums)

	const NEG_INF int64 = -1 << 60

	dp1 := make([]int64, n)
	dp2 := make([]int64, n)
	dp3 := make([]int64, n)

	for i := 0; i < n; i++ {
		dp1[i] = NEG_INF
		dp2[i] = NEG_INF
		dp3[i] = NEG_INF
	}

	ans := NEG_INF

	for i := 1; i < n; i++ {
		if nums[i-1] < nums[i] {
			startInc := int64(nums[i-1]) + int64(nums[i])
			extendInc := dp1[i-1] + int64(nums[i])

			if startInc > extendInc {
				dp1[i] = startInc
			} else {
				dp1[i] = extendInc
			}

			startFinal := dp2[i-1] + int64(nums[i])
			extendFinal := dp3[i-1] + int64(nums[i])

			if startFinal > extendFinal {
				dp3[i] = startFinal
			} else {
				dp3[i] = extendFinal
			}
		}

		if nums[i-1] > nums[i] {
			startDec := dp1[i-1] + int64(nums[i])
			extendDec := dp2[i-1] + int64(nums[i])

			if startDec > extendDec {
				dp2[i] = startDec
			} else {
				dp2[i] = extendDec
			}
		}

		if dp3[i] > ans {
			ans = dp3[i]
		}
	}

	return ans
}

The Go implementation is identical in logic to the Python version.

One important difference is numeric type handling. Since values can reach 10^9 and the array length can reach 100,000, the total sum can be as large as approximately 10^14. Therefore int64 is required for all DP states and for the return value.

Worked Examples

Example 1

Input:

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

DP evolution:

i nums[i] dp1 dp2 dp3
0 0 - - -
1 -2 invalid invalid invalid
2 -1 -3 invalid invalid
3 -3 invalid -6 invalid
4 0 -3 invalid -6
5 2 2 invalid -4
6 -1 invalid 1 invalid

The largest value appearing in dp3 is:

-4

which is the answer.

Example 2

Input:

[1, 4, 2, 7]

DP evolution:

i nums[i] dp1 dp2 dp3
0 1 - - -
1 4 5 - -
2 2 - 7 -
3 7 9 - 14

The maximum value in dp3 is:

14

which corresponds to the entire array.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single left-to-right pass
Space O(n) Three DP arrays of length n

The algorithm performs constant work for every index. No nested loops are used, so the running time is linear. The DP arrays each store one value per position, giving linear memory usage.

Test Cases

sol = Solution()

assert sol.maxSumTrionic([0, -2, -1, -3, 0, 2, -1]) == -4  # example 1
assert sol.maxSumTrionic([1, 4, 2, 7]) == 14  # example 2

assert sol.maxSumTrionic([1, 2, 1, 2]) == 6  # smallest valid shape

assert sol.maxSumTrionic([-5, -3, -6, -2]) == -16  # all negative

assert sol.maxSumTrionic([1, 5, 3, 2, 4]) == 15  # longer decreasing phase

assert sol.maxSumTrionic([1, 2, 3, 1, 2, 3]) == 12  # long first increase

assert sol.maxSumTrionic([10, 20, 5, 15]) == 50  # entire array optimal

assert sol.maxSumTrionic([-10, 100, -20, 200]) == 270  # large positive gain

assert sol.maxSumTrionic([1, 3, 2, 4, 3, 5]) == 15  # multiple candidates

assert sol.maxSumTrionic([2, 5, 1, 3, 4]) == 15  # extend final increase

Test Summary

Test Why
[0,-2,-1,-3,0,2,-1] Official example with negative answer
[1,4,2,7] Official example
[1,2,1,2] Minimum valid trionic length
[-5,-3,-6,-2] All numbers negative
[1,5,3,2,4] Longer decreasing section
[1,2,3,1,2,3] Long initial increase
[10,20,5,15] Entire array forms trionic pattern
[-10,100,-20,200] Large positive contribution after valley
[1,3,2,4,3,5] Multiple competing trionic subarrays
[2,5,1,3,4] Final increasing phase extension

Edge Cases

All Values Are Negative

A common mistake is assuming the answer must be positive and initializing the result to zero. In arrays containing only negative numbers, every valid trionic subarray also has a negative sum. The implementation uses a very small negative sentinel value (NEG_INF) and therefore correctly returns the largest negative trionic sum.

Equal Adjacent Values

The problem requires strict inequalities. If nums[i-1] == nums[i], that edge can belong to neither an increasing nor a decreasing segment. The transitions only occur when < or > holds, so equal values automatically break any ongoing monotonic structure.

Starting a New Phase

Another subtle bug is allowing a phase transition before the previous phase actually exists. For example, the decreasing phase must start from a valid increasing segment, and the final increasing phase must start from a valid increasing-decreasing structure. The DP transitions enforce exactly this requirement by only constructing dp2 from dp1 and only constructing dp3 from dp2.

Large Sums

The maximum possible subarray sum can be roughly:

100000 * 10^9 = 10^14

which exceeds 32-bit integer limits. The Go solution therefore stores all DP values in int64, and the Python solution naturally supports arbitrarily large integers.