Longest Increasing Subsequence

medium

Acceptance: 47%

Dynamic ProgrammingBinary Search

Given an array of integers, find the length of the longest subsequence whose elements are in strictly ascending order. Elements of the subsequence need not be contiguous but must preserve their relative positions from the original array.

Examples

Example 1:

Input:nums = [3,1,4,1,5,9,2,6]

Output:4

Explanation: One longest increasing subsequence is [1,4,5,9], which has length 4.

Example 2:

Input:nums = [5,2,8,6,3,6,9]

Output:4

Explanation: One longest increasing subsequence is [2,3,6,9].

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Longest Increasing Subsequence

Examples

Hints

Related Problems