# Leetcode 300 - Longest Increasing Subsequence

### Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

### Understanding the problem

The problem statement on LeetCode reads as follows:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Explanation: The longest increasing subsequence is [0,1,3,5], therefore the length is 4.

### Plan your solution

One way to solve this problem is to use dynamic programming. We can create a table ** dp** where

**represents the length of the longest increasing subsequence ending at index**

`dp[i]`

**in the input array. Then, we can iterate through the input array and for each element, we can check the previous elements and update the**

`i`

**table accordingly. Specifically, for each element**

`dp`

**, we can set**

`nums[i]`

**to be the maximum of**

`dp[i]`

**for all**

`dp[j] + 1`

**such that**

`j`

**and**

`j < i`

**. Finally, we can return the maximum value in the**

`nums[j] < nums[i]`

**table.**

`dp`

### Implement your solution

Now that we have a plan, let’s implement it in Python.

```
class Solution:
def lengthOfLIS(self, nums):
# Edge case: if the array is empty, return 0
if not nums:
return 0
# Initialize the dp table with all 1s
dp = [1] * len(nums)
# Iterate through the array
for i in range(1, len(nums)):
# Iterate through the previous elements
for j in range(i):
# If the current element is greater than the previous element, update the dp table
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
# Return the maximum value in the dp table
return max(dp)
```

### Test your solution

Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Longest Increasing Subsequence” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with an array that is sorted in increasing order, an array that is sorted in decreasing order, an array that has all the same elements, and an array that has no increasing subsequences. We can also test our solution with arrays of different lengths and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

### Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

**Related:**