DP or 贪心 + 二分答案：最长上升子序列Ⅰ

雨点打透心脏的1/2处 2023-10-06 20:38 70阅读 0赞

## DP or 贪心 + 二分答案：最长上升子序列Ⅰ ##

#### 文章目录 ####

*  DP or 贪心 + 二分答案：最长上升子序列Ⅰ
 *   *   *  问题
         *  思路
         *   *  DP（ O(n ^ 2）)
             *  代码
             *  贪心 + 二分答案(最优解，O(nlogn))
             *  代码

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

##### DP（ O(n ^ 2）) #####

一个数若能加入在其之前的某个上升子序列，则该数一定大于位于其之前的某上升子序列的最后一个元素（最大的元素）。我们用DP\[i\]表示以第i个数结尾的最长上升子序列的长度。那么DP\[i\]是如何经状态转移得到的呢？设数组为a\[\]，对于第i个数a\[i\]，它有可能加入在其之前以任意某个数a\[j\]结尾的上升子序列，也就是说DP\[i\]可能由DP\[j\]转移得到，这里需满足`j < i,a[i] > a[j]`。那么状态转移方程为：  
![在这里插入图片描述][0dcf7bf1216b4ef49cdb56478048653c.png]

即状态转移时，我们需往前面遍历，找到一个a\[i\]>a\[j\]，且DP\[j\]最大的，将其继承过来，也就是将a\[i\]加入其代表的上升子序列

##### 代码 #####

import java.util.*;
    
    public class Main {
        
        static int[] array = new int[1005];
        static int[] dp = new int[1005];
        public static void main(String[] args) {
        
            int n, ans, i, j;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                for (i = 1;i <= n;i++) {
        
                    array[i] = scanner.nextInt();
                }
                Arrays.fill(dp, 0);
                ans = 0;
                for (i = 1;i <= n;i++) {
        
                    for (j = 0;j < i;j++) {
        
                        if (array[i] > array[j]) {
        
                            dp[i] = Math.max(dp[i], dp[j] + 1);
                        }
                    }
                    ans = Math.max(ans, dp[i]);
                }
                System.out.println(ans);
            }
        }
    }

##### 贪心 + 二分答案(最优解，O(nlogn)) #####

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d\[i\] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d\[1\] = nums\[0\]。

贪心思想，对于每个数x，要把它放到小于当前x的最大的d\[len\]后，之后更新长度len

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums\[i\] 时：

在 d 数组中二分查找，找到第一个比 nums\[i\] 小的数 d\[k\] ，并更新 d\[k + 1\] = nums\[i\]，再更新长度len。

d\[i\]数组是单调的，因此可以用二分查找（证明可以用反证法）

##### 代码 #####

import java.util.*;
    
    public class Main {
        
    
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                int n = scanner.nextInt();
                int[] array = new int[n];
                int i, len = 0;
                for (i = 0; i < n; i++) {
        
                    array[i] = scanner.nextInt();
                }
                int[] d = new int[n + 1];
                for (i = 0; i < n; i++) {
        
                    int l = 0;
                    int r = len;
                    while (l < r) {
        
                        int mid = (l + r + 1) / 2;
                        if (d[mid] < array[i]) {
        
                            l = mid;
                        } else {
        
                            r = mid - 1;
                        }
                    }
                    d[l + 1] = array[i];
                    len = Math.max(len, l + 1);
                }
                System.out.println(len);
            }
        }
    
    
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/48ad602d66b04f868e010fa7aeab9ee4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/57f049e8240f45c48309bddd5296b980.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[0dcf7bf1216b4ef49cdb56478048653c.png]: https://img-blog.csdnimg.cn/0dcf7bf1216b4ef49cdb56478048653c.png