Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Solution: Longest Increasing Subsequence

Problem Statement

Given a number sequence, find the length of its Longest Increasing Subsequence (LIS). In an increasing subsequence, all the elements are in increasing order (from lowest to highest).

Example 1:

Input: {4,2,3,6,10,1,12}
Output: 5
Explanation: The LIS is {2,3,6,10,12}.

Example 1:

Input: {-4,10,3,7,15}
Output: 4
Explanation: The LIS is {-4,3,7,15}.

Constraints:

  • 1 <= nums.length <= 2500
  • -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

For bottom up, why keep track of max length instead of just returning dp[n-1]?

D

David

· 4 years ago

For top-down DP:

I can't seem to pass test case 24 using a dictionary in C# with this method on Leetcode. It works fine with a 2D matrix, however. Not sure why that is...