Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Once an increasing run turns downward and then upward, its decreasing middle must be included in full. The choices are how far to extend into the increasing run before it and the increasing run after it. Negative values mean taking those entire outer runs is not always best.

Approach

Scan to find a peak reached by at least one increasing step. Begin the candidate with the peak and its predecessor, then add the full strictly decreasing run through its valley. Reject this candidate if there is no decreasing step or no following increasing step.

Include the first value after the valley to guarantee a nonempty final increase. Extend forward through that increasing run, retaining the largest additional prefix sum, with zero allowing no extension. Similarly scan backward from before the peak's predecessor and retain the best additional suffix of the preceding increasing run. Add both best extensions to the mandatory middle and update the answer.

Resume at the valley because the final increasing run can begin the next candidate. Strict comparisons prevent equal adjacent values from joining a trionic segment, and initializing the answer to negative infinity allows an all-negative valid result.

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)
        res = -inf
        i = 0

        while i < n:
            # shortest first segment
            j = i + 1
            while j < n and nums[j] > nums[j - 1]:
                j += 1
            p = j - 1

            if p == i:
                i += 1
                continue

            curr = nums[p] + nums[p - 1]

            # full second segment
            while j < n and nums[j] < nums[j - 1]:
                curr += nums[j]
                j += 1

            q = j - 1

            if p == q or q == n - 1 or (q < n - 1 and nums[q] == nums[j]):
                i = q
                continue

            # third segment with max sum
            curr += nums[j]
            j += 1

            acc = 0
            mx = 0
            while j < n and nums[j] > nums[j - 1]:
                acc += nums[j]
                mx = max(mx, acc)
                j += 1
            curr += mx

            # maximize the sum of first segment
            acc = 0
            mx = 0
            jj = p - 2
            while jj >= 0 and nums[jj] < nums[jj + 1]:
                acc += nums[jj]
                mx = max(mx, acc)
                jj -= 1
            curr += mx

            res = max(res, curr)
            i = q # next possible trionic starts with the last segment

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1).