鞍山市网站建设_网站建设公司_支付系统_seo优化

2026-01-11：三段式数组Ⅱ。用go语言，给定长度为 n 的整数序列 nums，要求选出一个包含至少四个元素的连续区间 [a, b]（0 ≤ a < b < n），并在区间内选两个切分点 a < i < j < b，使得区间被分成三段：第一段从 a 到 i 元素严格上升，第二段从 i 到 j 元素严格下降，第三段从 j 到 b 元素又严格上升。在所有满足此模式的连续区间中，找出其元素和的最大值并返回该最大和。

4 <= n = nums.length <= 100000。

-1000000000 <= nums[i] <= 1000000000。

保证至少存在一个三段式子数组。

输入: nums = [1,4,2,7]。

输出: 14。

解释:

选择 l = 0, p = 1, q = 2, r = 3：

nums[l…p] = nums[0…1] = [1, 4] 严格递增 (1 < 4)。

nums[p…q] = nums[1…2] = [4, 2] 严格递减 (4 > 2)。

nums[q…r] = nums[2…3] = [2, 7] 严格递增 (2 < 7)。

和 = 1 + 4 + 2 + 7 = 14。

题目来自力扣3640。

🔍 算法步骤详解

1. 初始化阶段
   算法定义了四个关键变量，并赋予它们一个极小的初始值（negInf，约为最小整数的一半，以防止后续加法运算时溢出）：

   • ans：用于记录遍历过程中找到的满足条件的最大子数组和。
   • f1：动态规划状态变量，追踪当前可能处于**第一段（严格递增）**的序列的最大和。
   • f2：动态规划状态变量，追踪当前可能处于**第二段（严格递减）**的序列的最大和。
   • f3：动态规划状态变量，追踪当前可能处于**第三段（严格递增）**的序列的最大和。

2. 遍历与状态转移
   算法从数组的第二个元素开始遍历（i从 1 到len(nums)-1）。在每一步，它比较当前元素y（即nums[i]）和前一个元素x（即nums[i-1]），并根据大小关系更新三个状态变量：

   • 情况一：x < y（上升趋势）
     这种情况可能意味着延续第一段的上升，或者开启第三段的上升。

     • 更新f3（第三段）：f3可以从上一状态f3（延续第三段）或f2（第二段结束，开始第三段）转移过来，并加上当前元素y。然后，用这个新的f3值尝试更新全局最大和ans。
     • 更新f1（第一段）：f1可以从其上一状态延续并加上y，这表示第一段在延长。
     • 重置f2：由于出现了上升趋势，任何正在构建的第二段（下降段）必须中断，因此将f2重置为negInf。

   • 情况二：x > y（下降趋势）
     这种情况可能意味着从第一段过渡到第二段，或者延续第二段的下降。

     • 更新f2（第二段）：f2可以从其上一状态延续，或者从f1（第一段结束，开始第二段）转移过来，并加上当前元素y。
     • 重置f1和f3：一旦进入下降趋势，之前可能的第一段和第三段状态变得无效，因此将f1和f3重置为negInf。

   • 情况三：x == y（相等元素）
     根据题目要求，每一段都必须是“严格”单调的。因此，只要出现相邻元素相等，当前正在构建的任何三段式模式都会立即失效。

     • 完全重置状态：将f1,f2,f3全部重置为negInf，表示需要重新开始寻找有效的序列模式。

3. 结果返回
   在遍历完整个数组后，变量ans中存储的就是所有满足条件的三段式连续子数组的最大和，算法将其转换为int64类型后返回。

⏱️ 复杂度分析

• 时间复杂度：O(n)
  算法仅对输入数组nums进行了一次线性遍历，循环内的所有操作（比较、加法、取最大值）都是常数时间O(1)。因此，总的时间复杂度与数组长度n成线性关系，为O(n)。

• 额外空间复杂度：O(1)
  算法在执行过程中，仅使用了固定数量的额外变量（ans,f1,f2,f3,i,x,y）。这些变量的数量不随输入数组的大小n而变化。因此，额外的空间复杂度是常数阶O(1)。

Go完整代码如下：

packagemainimport("fmt""math")funcmaxSumTrionic(nums[]int)int64{constnegInf=math.MinInt/2// 除 2 防止下面加法（和负数相加）溢出ans,f1,f2,f3:=negInf,negInf,negInf,negInffori:=1;i<len(nums);i++{x,y:=nums[i-1],nums[i]ifx<y{// 第一段或者第三段f3=max(f3,f2)+y ans=max(ans,f3)f2=negInf f1=max(f1,x)+y}elseifx>y{// 第二段f2=max(f2,f1)+y f1,f3=negInf,negInf}else{f1,f2,f3=negInf,negInf,negInf}}returnint64(ans)}funcmain(){nums:=[]int{1,4,2,7}result:=maxSumTrionic(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defmaxSumTrionic(nums):NEG_INF=-10**18# 使用一个足够小的负数，避免溢出ans=f1=f2=f3=NEG_INFforiinrange(1,len(nums)):x,y=nums[i-1],nums[i]ifx<y:# 第一段或者第三段f3=max(f3,f2)+y ans=max(ans,f3)f2=NEG_INF f1=max(f1,x)+yelifx>y:# 第二段f2=max(f2,f1)+y f1=f3=NEG_INFelse:f1=f2=f3=NEG_INFreturnansif__name__=="__main__":nums=[1,4,2,7]result=maxSumTrionic(nums)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<climits>#include<algorithm>usingnamespacestd;longlongmaxSumTrionic(vector<int>&nums){constlonglongNEG_INF=LLONG_MIN/2;// 除 2 防止加法溢出longlongans=NEG_INF,f1=NEG_INF,f2=NEG_INF,f3=NEG_INF;for(size_t i=1;i<nums.size();i++){intx=nums[i-1],y=nums[i];if(x<y){// 第一段或者第三段f3=max(f3,f2)+y;ans=max(ans,f3);f2=NEG_INF;f1=max(f1,(longlong)x)+y;}elseif(x>y){// 第二段f2=max(f2,f1)+y;f1=f3=NEG_INF;}else{f1=f2=f3=NEG_INF;}}returnans;}intmain(){vector<int>nums={1,4,2,7};longlongresult=maxSumTrionic(nums);cout<<result<<endl;return0;}