后端开发刷题 | 最长上升子序列

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j 且 arri​≥arrj​。

数据范围： 0≤n≤1000

要求：时间复杂度 O(n2)， 空间复杂度 O(n)

示例1

输入：

[6,3,1,5,2,3,7]

返回值：

4

说明：

该数组最长上升子序列为 [1,2,3,7] ，长度为4

思路分析：

该题可以使用动态规划来解决

1. 特殊情况处理：
   • 首先，检查输入数组arr是否为空。如果为空，则直接返回0，因为空数组不包含任何子序列。
2. 动态规划数组初始化：
   • 创建一个与输入数组arr等长的数组dp，用于存储以每个元素结尾的最长严格上升子序列的长度。初始时，假设每个元素自身构成一个长度为1的子序列，因此将dp数组的所有元素初始化为1。
3. 动态规划过程：
   • 使用两层嵌套的循环来填充dp数组。外层循环遍历数组arr的每个元素（记作arr[i]），内层循环遍历当前元素之前的所有元素（记作arr[j]，其中j < i）。
   • 对于每一对arr[i]和arr[j]，如果arr[i]大于arr[j]，则说明arr[i]可以接在arr[j]后面形成一个更长的严格上升子序列。此时，更新dp[i]为dp[j] + 1和dp[i]的较大值，以记录以arr[i]结尾的最长严格上升子序列的长度。
4. 结果计算：
   • 使用Arrays.stream(dp).max().getAsInt()从dp数组中找到最大值，这个最大值就是整个数组arr的最长严格上升子序列的长度。这里使用了Java 8的Stream API来简化数组的最大值查找过程。
5. 返回值：
   • 返回计算得到的最长严格上升子序列的长度。

代码：

import java.util.*;


public class Solution {
    /**
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        //特殊情况
        if(arr.length==0){
            return 0;
        }
        int[] dp=new int[arr.length];
        
        //初始化状态数组
        Arrays.fill(dp,1);
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}