Maximum Sum of an Increasing-Decreasing-Increasing Subarray

### Problem You are given an integer array `nums`. Consider a contiguous subarray `nums[l...r]` for which there are 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. Each part therefore contains at least one step between distinct adjacent values. The parts share their turning endpoints, and each array element contributes to the subarray sum only once. Return the largest sum of any such subarray. At least one valid subarray is guaranteed to exist. ```cpp class Solution { public: long long maxSumTrionic(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text Input: nums = [2,5,1,4,6] Output: 18 Explanation: Choose the whole array, with turning indices p = 1 and q = 2. Its parts are [2,5], [5,1], and [1,4,6]. Its sum is 2 + 5 + 1 + 4 + 6 = 18. Every entry is positive, so no subarray can have a larger sum. ``` **Example 2:** ```text Input: nums = [-7,-2,-5,-1] Output: -15 Explanation: The only possible valid subarray uses all four elements: -7 < -2 > -5 < -1. Its sum is -15. Returning zero would incorrectly allow an empty selection. ``` ### Constraints - `4 <= nums.length <= 100000`. - `-1000000000 <= nums[i] <= 1000000000`. - At least one subarray with the stated three strict parts exists. ### Clarifying Questions - Is a subsequence allowed? No. The selected elements must be contiguous. - May one of the three parts have no step? No. The indices satisfy `l < p < q < r`. - Can equal adjacent values belong to one of the parts? No; every required comparison is strict. - Must the answer be nonnegative? No. The best valid sum may be negative. - Are the turning elements added twice? No. Sum the selected array positions once each. ### What a Strong Answer Covers - All three strict parts, their nonempty steps, and the contiguous-subarray requirement. - Correct sums when the best answer is negative or a turning element belongs to two parts. - Equal adjacent values and the full input-length bound. - An optimality argument, resource bounds, and arithmetic suitable for large sums. ### Follow-up Questions - What behavior would need to be specified if the existence guarantee were removed? - How do equal adjacent values affect the set of valid subarrays? ```hint Track which comparisons have already occurred Keep the best sum ending at the current position for each valid progress stage. Starting the first increasing part must remain possible at a new adjacent pair, even when extending an older increasing prefix would lower its sum. ```