思路:最长上升子序列(LIS)的优化以及应用

大家先学习LIS以及其优化方法:https://leetcode.cn/circle/discuss/r3ucvm/

在知道这个知识点以后，我们不难想出，任意一个山峰序列都是由：山峰+ 山峰往左的LIS + 山峰往右的LIS 组成的。

例如:1 , 1 , 5 , 4 , 1 中 5(山峰) + [1 , 5] (山峰以左的LIS) + [5 , 4 , 1] (山峰以右的LIS)

那么我们只需要正反两遍dp求出dp[i]代表以arr[i]为结尾的LIS的最大长度。然后拼接答案即可

由于n 比较大，我们可以使用树状数组优化或者二分先求dp[i]代表长度为i的LIS的最小结尾。然后每次用arr[i]在dp里二分找下标时，这个下标就是以arr[i]为结尾的LIS的最大长度。

代码

python

n = int(input())
a = list(map(int, input().split()))
def get_LIS (a):
    dp = [0]
    cnt = 0
    # dp[i]代表长度为i的LIS的最小结尾
    res = []
    for x in a:
        if x > dp[cnt]:
            dp.append(x)
            cnt += 1
            # 以x结尾的LIS长度为cnt
            res.append(cnt)
        else:
            l = 0
            r = cnt
            while l <= r:
                mid = (l + r) // 2
                if dp[mid] < x:
                    l = mid + 1
                else:
                    r = mid - 1
            dp[l] = x
            # 以x结尾的LIS长度为l
            res.append(l)
    return res
# 正反两次LIS
res_1 = get_LIS(a)
res_2 = get_LIS(a[::-1])[::-1]
mx = -1
for i in range(n):
    mx = max(mx, res_1[i] + res_2[i] - 1)
print(mx)
    

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目描述

小红定义一个长度为$n$的数组为“山峰数组”:存在这样的一个位置，使得这个位置左右两边的全部元素均依次严格递减;使用数学的语言来描述，即存在$x∈(1,n)$使得$a_{i-1}<a_i(i ∈[x,n])$且$a_i>a_{i+1}(i∈[1,x])$。例如 $[1,2,5,4,2]$和$[1,3,2]$是“山峰数组”而$[1],[1,2,3],[1,2,1,2]$和$[1,2,1,1]$不是“山峰数组”。

小红有一个长度为$n$的数组$a_1,a_2,…,a_n$，他想知道在全部的子数组✟中，是“山峰数组”的子数组的长度最大值是多少。

✟:如果数组$a$可以通过从数组$b$的开头删除若干(可能为零或全部)元素以及从结尾删除若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子数组。

输入描述

第一行输入一个整数$n(1≤n≤10^5)$代表数组长度。

第二行输入$n$个整数$a_1,a_2,… ,a_n(1≤a≤10^9)$代表数组的值。

输出描述

在一行上输出一个正整数，代表长度的最大值。

样例1

输入

6
1 1 4 5 1 4

输出

4

提示

最长的“山峰函数“是$[1,4,5,1]$。

样例2

输入

4
1 2 2 1

输出

3