LeetCode link

first thought

  • DP. Using 1d array to record the maximum length of sequence of each number when the number is the last number in the sequence.
  • Get the maximum number of the array.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 0;
        for (int i = 1; i < n; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] > count) {
                    count = dp[j];
                }
            }
            dp[i] = count + 1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

result

AC.

Follow Up

Using nlogn time complexity.

thought

  • There should be some solution connecting to binary search which is O(logn).
  • But the input is unsorted, so maybe it’s not to search some specific value in the input array.
  • Still a little confused. Update later.