#3640

Trionic Array II

hard · 47.3% accepted · 381 likes · top 32%

array · dynamic programming

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

Solution