数据结构与算法-动态规划- 最长递增子序列

最长递增子序列

给你一个整数数组?nums?，找到其中最长严格递增子序列的长度。

子序列?是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]?是数组?[0,3,1,6,2,2,7]?的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• 104 <= nums[i] <= 104

思路：

1. dp[i] 表示arr[0….i] 中最长序列长度
2. dp[0] = 1;
3. 假设计算到 i，那么在arr[0….i-1] 中只要比arr[i]小的都可以作为倒数第二个数，但是在众多倒数第二个数的选择中，哪个最长序列长度最大，就选择哪个数。dp[i] =max(dp[j]+1) 如果没有比arr[i]小的数，则dp[i]=1。

代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = process(nums);
        return generateLIS(nums,dp);

    }

    public  int generateLIS(int[] arr,int[] dp) {
        int length = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if(dp[i] > length) {
                length = dp[i];
                index = i;
            }
        }

        return length;

    }

    public  int[] process (int[] arr) {
        int[] dp = new int[arr.length];
        if( arr.length==0) {
            return dp;
        }

        dp[0] = 1;
        for(int i =0;i<arr.length;i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(arr[j]<arr[i]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }

        return dp;

    }
}