777. Longest Increasing Subsequence (Recursive + Memoization)

Given an integer array nums, return the LENGTH of the longest STRICTLY increasing subsequence. A subsequence is a sequence derived by deleting some (possibly zero) elements without changing the relative order. If nums is empty, return 0. Implement with recursion + memoization.

Input: An integer array nums.

Output: Return an integer — the longest strictly increasing subsequence length.

Examples

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: One LIS is [2,3,7,101] with length 4.

Input: [7,7,7,7]
Output: 1
Explanation: All equal, strict increase requires length 1.

Input: [0,1,0,3,2,3]
Output: 4
Explanation: One LIS is [0,1,2,3].

Constraints

• 0 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9

Asked by