*<1> 编程求出数列的所有升或降的最大子序列。如下面数列的解为如下: 1,20,30,12,3,5,7,4,6,100,11,8 (1,20,30),(30,12,3),(3,5,7),(7,4),(4,6,100),(100,11,8)。
时间: 2023-10-30 19:08:07 浏览: 54
该问题可以使用动态规划算法来解决。具体步骤如下:
1. 定义两个数组up和down,分别表示以当前元素为结尾的最长上升子序列和最长下降子序列。
2. 初始化up和down数组的第一个元素为1。
3. 从第二个元素开始遍历整个数列,对于每个元素,分别计算以该元素为结尾的最长上升子序列和最长下降子序列。
4. 遍历完整个数列后,根据up和down数组的结果,构造出所有的最长升、降子序列。
具体实现可以参考下面的代码:
```
def findMaxSubsequence(nums):
n = len(nums)
up = [1] * n
down = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
up[i] = max(up[i], up[j] + 1)
elif nums[i] < nums[j]:
down[i] = max(down[i], down[j] + 1)
maxLen = max(max(up), max(down))
res = []
for i in range(n):
if up[i] == maxLen:
subseq = [nums[i]]
for j in range(i - 1, -1, -1):
if nums[j] < nums[i] and up[j] == up[i] - 1:
subseq.insert(0, nums[j])
i = j
res.append(subseq)
if down[i] == maxLen:
subseq = [nums[i]]
for j in range(i - 1, -1, -1):
if nums[j] > nums[i] and down[j] == down[i] - 1:
subseq.insert(0, nums[j])
i = j
res.append(subseq)
return res
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)