1. 解题思路
这一题是题目3637. Trionic Array I的进阶版本，事实上就是要考察一个数组当中能够构成的所有trionic array当中和最大的一个结果。
而对于一个trionic array，其事实上就包含三段，即开头和结尾的递增数组以及中间的递减数组。由于整体的subarray是连续的，因此中间的递减数组是无法改动的，因此要获得最大的和，事实上我们就是要在这个递减数组的前后找到分别以两端作为结尾和开头的两个连续递增数组的和的最大值。
因此，我们只需要提前计算出每一个节点作为一个递增序列的头节点和尾节点时能够获取的最大的和，那么我们只需要遍历一下每一段连续递减的子数组即可得到我们最终的结果。
而要求取每一个节点分别作为头节点和尾节点时其能获取的最大的和，我们事实上只需要是用动态规划即可快速得到。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxSumTrionic(self, nums: List[int]) -> int:
n = len(nums)
dp1 = [-math.inf for _ in range(n)] # max inc start with idx
for i in range(n-2, -1, -1):
if nums[i+1] > nums[i]:
dp1[i] = max(nums[i] + nums[i+1], nums[i] + dp1[i+1])
dp2 = [-math.inf for _ in range(n)] # max inc end with idx
for i in range(1, n):
if nums[i] > nums[i-1]:
dp2[i] = max(nums[i] + nums[i-1], nums[i] + dp2[i-1])
ans = -math.inf
i, j = 1, 2
while j < n-1:
if nums[j] >= nums[i]:
i, j = j, j+1
continue
s = nums[i]
while j < n-1 and nums[j] < nums[j-1]:
s += nums[j]
j += 1
j -= 1
ans = max(ans, s+dp1[j]+dp2[i]-nums[i]-nums[j])
i, j = j, j+1
return ans
提交代码评测得到：耗时403ms，占用内存35.38MB。