张仁翔

用户名：dotcpp0698394

访问量：932

签　名：

等　　级
排　　名	1759
经　　验	2659
参赛次数	7
文章发表	2
年　　龄	0
在职情况	学生
学　　校	长江大学文理学院
专　　业

　　自我简介：

自闭患者

TA的其他文章

蓝桥真题(最长接龙序列)详解dp！两种解题策略体现不同dp思路求解差异巨大！
浏览：733

你可能喜欢

最长上升子序列优化之构造辅助数组(贪心思想)

　　作者: 张仁翔　　　　发表时间：2024-03-21 22:29:16 浏览：126　|　评论：0　

原题链接：最长上升子序列

# 最长上升子序列优化——辅助数组

**思路参考：陈小玉老师的《趣学算法》**

**思路：我们先定义辅助数组d[]，长度为序列长度，辅助变量int len 来记录d里面的元素个数, 初始化d[0] = arr[0],len = 1,然后依次遍历接下来的元素arr[i],如果arr[i] > d[len]，是上升序列，符合条件，那么直接把arr[i]加入到d[len]里面，同时len++，如果arr[i] = d[len],因为相等了，所以不做处理，进行下一次循环比较，如果arr[i] < d[len]，那么找到数组d里面第一个比arr[i]大的数的索引index（因为d本身有序，所以可以使用二分搜索进行查找，java代码有具体实现，C++标准模板库中有具体的实现函数lower_bound() ），把arr[i] =的值赋给d[index]，依次循环遍历，len即为所求。
因为如果递增序列的数越小，那么能递增的长度也就越大，因此第三步的操作就是如果不做添加时，即len不变时，让较小的数替换到原来较大的数，那么所得序列的长度即可达到最大。**

**时间复杂度：由于所有的数都要遍历一遍复杂度为O(n)，且二分搜索时间复杂度为O(logn) 那么总的时间复杂度为 O(nlogn),优于动态规划求解(O(n^2))。**
**空间复杂度：设有一个辅助数组d，故空间复杂度为O(n)。**

###### 求解过程
|  i | arr[i]  | d[i]  | len  | 比较arr[i]和 d[len] |
| ------------ | ------------ | ------------ | ------------ | ------------ |
| 1 |  **1** 7 3 5 9 4 8 | **1** | 1 | 初始化 |
| 2 | 1 **7 **3 5 9 4 8 |  1 **7** | 2  |  arr[2]>d[1]，直接将arr[2]放在d[]尾部，同时len++ |
| 3 |  1 7 **3** 5 9 4 8 | 1 **3**| 2| arr[3]<d[2]，那么让arr[3]替换掉第一次大于或等于它的元素|
| 4 | 1 7 3 **5** 9 4 8  | 1 3 **5**|3| arr[4]>d[2]，直接将arr[4] 放在d[]的尾部，同时len++|
| 5 | 1 7 3 5 **9** 4 8  |  1 3 5 **9** | 4  |  arr[5]>d[3]，直接将arr[5]放在d[]尾部，同时len++ |
| 6 |  1 7 3 5 9 **4** 8 | 1 3 **4** 9  | 4  | arr[6]<d[4]，那么让arr[6]替换掉第一次大于或等于它的元素  |
| 7 | 1 7 3 5 9 4 **8**  | 1 3 4 **8**  |  4 |  arr[7]<d[4]，那么让arr[7]替换掉第一次大于或等于它的元素 |

- #### Java代码如下
```java
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i){
            arr[i] = scanner.nextInt();
        }
        System.out.println(help(arr));
    }
    public static int help(int[] arr){
        int len = 0;
        int[] d = new int[arr.length];
        d[0] = arr[0];
        len = 1;
        for (int i = 1; i < arr.length; ++i){
            if (arr[i] > d[len - 1]) {
                // 直接加到d数组的后头;
                d[len++] = arr[i];
            } else if (arr[i] == d[len - 1]){
                continue;
            } else {
                int index = firstIndexGreaterThanOrEqualSpecifiedNum(d, len, arr[i]);
                d[index] = arr[i];
            }
        }
        return len;
    }
    /**
     * 找到第一个大于指定数key索引
     * @param arr 范围数组
     * @param len 查询长度 0-len(被包括)
     * @param key 查询的指定值 就是第一次比这个数大的索引
     * @return 目标索引
     */
    public static int firstIndexGreaterThanOrEqualSpecifiedNum(int[] arr, int len , int key) {
        // 使用 二分搜索进行查找;
        int left = 0 , right = len;
        int middle;
        int index = -1;
        while (left <= right){
            middle = (right - left) / 2 + left;
            if (arr[middle] >= key){
                index = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return index;
    }
}
```

- #### C++代码如下
**C++可以直接调用库函数里面的lower_bound()函数来得到第一个大于或等于c[i]的数**
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n;++i){
        cin >> c[i];
    }
    int d[n];
    int len = 1;
    d[0] = c[0];
    for (int i = 1; i < n; ++i){
        if (c[i] > d[len - 1]) d[len++] = c[i];
		else if (c[i] == d[len - 1]) continue;
        else  {
            *lower_bound(d , d + len , c[i])=c[i];
        }
    }
    cout << len << endl;
    return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

张仁翔

TA的其他文章

你可能喜欢

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求函数值（C语言代码）

最长上升子序列优化之构造辅助数组(贪心思想)

评论区

精彩推荐

兰顿蚂蚁（C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

幸运数（C++代码）

简单的a+b （C语言代码）

母牛的故事（java语言代码）

张仁翔

TA的其他文章

你可能喜欢

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言训练-角谷猜想 （C++代码）（3N+1问题）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求函数值 （C语言代码）

最长上升子序列优化之构造辅助数组(贪心思想)

评论区

精彩推荐

兰顿蚂蚁 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

幸运数 （C++代码）

简单的a+b （C语言代码）

母牛的故事 （java语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言训练-求函数值（C语言代码）

　　评论区

兰顿蚂蚁（C++代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

用筛法求之N内的素数。（C语言代码）

幸运数（C++代码）

母牛的故事（java语言代码）