题解 | #求解立方根#

题解

改题为求 最长升序子序列问题

1.定义一个数组dp用于存储每个数最长子序列的数值，默认为1(因为一个数的时候他的最长序列为1)。

2.使用两个下标i,j（j<i）计算数组arr 与 对应dp的值；如果arr[i] > arr[j] 的时候；计算dp[i] 此时 dp[i] = Math.max(dp[i], dp[j]+1)；如下表为输入的arr与计算的dp关系。

3.定义一个max，用于存储最长的子序列值。

代码

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 初始化为1
        int max = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 当前的值比前面的值大的时候需要计算。
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(dp[i], max);
                }
            }
        }
        System.out.println(max);
    }
}