# Leetcode 300 - Longest Increasing Subsequence ### 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.

One way to solve this problem is to use dynamic programming. We can create a table `dp` where `dp[i]` represents the length of the longest increasing subsequence ending at index `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 `dp` table accordingly. Specifically, for each element `nums[i]`, we can set `dp[i]` to be the maximum of `dp[j] + 1` for all `j` such that `j < i` and `nums[j] < nums[i]`. Finally, we can return the maximum value in the `dp` table.

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 =  * 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)
``````