描述

给定一个长度为 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] + 1dp[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();
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部