leetcode 300. 整数数组的最长严格递增子序列的长度

Love The Way You Lie 2024-03-27 11:01 93阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package dynamicProgramming;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    import static java.lang.System.in;
    
    /**
     * leetcode  300. 整数数组的最长严格递增子序列的长度
     */
    public class Leetcode300LongestStrictlyIncreasingSubsequence {
        
        public static void main(String[] args) throws IOException {
        
            // 收集数据源
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            int[] arr = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            bf.close();
    
            int max = lengthOfLIS(arr);
    
            // 输出结果
            System.out.println(max);
        }
    
        /**
         * leetcode  300. 整数数组的最长严格递增子序列的长度
         */
        private static int lengthOfLIS(int[] nums) {
        
            if (nums.length == 0) {
        
                return 0;
            }
    
            // 参数初始化
            int[] dp = new int[nums.length];
            for (int i = 0; i < dp.length; i++) {
        
                dp[i] = 1; // 每个序列起码有自己所以长度最小为1
            }
    
            int max = 1; // 每个序列起码有自己所以长度最小为1
    
            for (int i = 1; i < nums.length; i++) {
        
                for (int j = 0; j < i; j++) {
         // 通过回放计算出dp[i]的最优值
                    if (nums[j] < nums[i]) {
        
                        dp[i] = Math.max(dp[j] + 1, dp[i]); // 状态转移方程
                    }
                }
    
                max = Math.max(dp[i], max); // dp[i]的最优值和max相比计算出max的最优值
            }
    
            return max;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://leetcode.cn/problems/longest-increasing-subsequence/