1. 题目

读题

HJ103 Redraiment的走法

考查点

2. 解法

思路

代码逻辑

具体实现

import java.util.Arrays;

// 动态规划求最长递增子序列长度
public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        // 数组为空，返回0
        if (nums == null || nums.length == 0) return 0;
        // 数组长度
        int n = nums.length;
        // dp数组，存储每个元素结尾的最长递增子序列长度
        int[] dp = new int[n];
        // 最长递增子序列长度
        int ans = 1;
        // 把dp数组的所有元素都设为1
        Arrays.fill(dp, 1);
        // 从左到右遍历原数组
        for (int i = 0; i < n; i++) {
            // 从左到右遍历i之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果nums[j] < nums[i]，更新dp[i]
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新ans
            ans = Math.max(ans, dp[i]);
        }
        // 返回ans
        return ans;
    }

    // 测试
    public static void main(String[] args) {
        // 示例数组
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        // 创建对象
        Solution solution = new Solution();
        // 调用函数
        int ans = solution.longestIncreasingSubsequence(nums);
        // 输出结果
        System.out.println("The length of the longest increasing subsequence is: " + ans);
    }
}

自行实现

public class HJ103 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(longestSeq(nums));
        sc.close();
    }

    public static int longestSeq(int[] nums) {

        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

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

                }
            }
        }

        return max;

    }
}

3. 总结