三段式数组 II
给你一个长度为 n 的整数数组 nums。
三段式子数组 是一个连续子数组 nums[l…r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：
nums[l…p] 严格 递增， nums[p…q] 严格 递减， nums[q…r] 严格 递增。 请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。
提示:
$4 <= n = nums.length <= 10^5$
$-10^9 <= nums[i] <= 10^9$
保证至少存在一个三段式子数组。
思路
由于l < p < q < r, $p$ 是第一段的终点和第二段的起点，$q$ 是第二段的终点和第三段的起点，我们可以通过预处理和线性扫描来解决。
-
preSum[i]: 以 $i$ 结尾且满足“严格递增”的最大子数组和。
条件：必须包含 $nums[i]$ 和 $nums[i-1]$。
公式：如果 $nums[i] > nums[i-1]$，$preSum[i] = \max(nums[i] + nums[i-1], preSum[i-1] + nums[i])$。
-
sufSum[i]: 以 $i$ 开头且满足“严格递增”的最大子数组和。
条件：必须包含 $nums[i]$ 和 $nums[i+1]$。
公式：如果 $nums[i] < nums[i+1]$，$sufSum[i] = \max(nums[i] + nums[i+1], sufSum[i+1] + nums[i])$。
如果前面的和已经变成负数，我们应当果断抛弃旧的部分，从当前能构成的最短合法子数组重新开始计算。
最后，我们枚举每一个可能的递减段 $[p…q]$。只要满足 $nums[p] > nums[p+1] > \dots > nums[q]$，我们就尝试用 preSum[p] + (中间段的和) + sufSum[q] 来更新答案。
点击展开/折叠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
long long maxSumTrionic(vector<int>& nums) {
int n = nums.size();
vector<long long > pre(n,LLONG_MIN),suf(n,LLONG_MIN);
for(int i=1;i<n;i++){
if(nums[i]>nums[i-1])
{
long long bs=(i>1&&pre[i-1]!=LLONG_MIN)?pre[i-1]:nums[i-1];
pre[i]=max((long long)nums[i]+nums[i-1],bs+nums[i]);
}
}
for(int i=n-2;i>=0;--i){
if(nums[i+1]>nums[i])
{
long long bs=(i+2<n&&suf[i+1]!=LLONG_MIN)?suf[i+1]:nums[i+1];
suf[i]=max((long long)nums[i+1]+nums[i],bs+nums[i]);
}
}
long long ans=LLONG_MIN;
for(int i=0;i<n-1;i++){
if(nums[i]>nums[i+1]){
int p=i;
long long t=nums[i];
while(i<n-1&&nums[i]>nums[i+1]){
++i;
t+=nums[i];
if(pre[p]!=LLONG_MIN&&suf[i]!=LLONG_MIN){
ans=max(ans,t+pre[p]+suf[i]-nums[i]-nums[p]);
}
}
i--;
}
}
return ans;
}
};
