Longest Increasing Subsequence - Leetcode Solution

The problem statement for the Longest Increasing Subsequence problem on LeetCode is as follows:

Given an unsorted array of integers, find the length of the longest increasing subsequence.

Example 1:

Input: [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: [0,1,0,3,2,3] Output: 4 Explanation: The longest increasing subsequence is [0, 1, 2, 3], therefore the length is 4.

Approach:

To solve this problem, we can use a dynamic programming approach. We can define a dp array where dp[i] stores the length of the longest increasing subsequence that ends with the element at index i. The maximum length of the longest increasing subsequence can then be obtained by finding the maximum value in the dp array.

The recurrence relation for the dp array can be defined as follows:

dp[i] = max(dp[j] + 1) where 0 <= j < i and nums[j] < nums[i]

We can start by initializing all elements in the dp array to 1 since a single element is always an increasing subsequence.

Algorithm:

1. Create a dp array of size n where n is the size of the input array nums.
2. Initialize all elements in the dp array to 1.
3. Loop through the input array nums from index 1 to n-1.
4. For each element at index i, loop through all elements from index 0 to i-1.
5. If the current element at index j is less than the element at index i, then update the dp array as follows: dp[i] = max(dp[i], dp[j] + 1)
6. Find the maximum value in the dp array and return it as the length of the longest increasing subsequence.

Code:

Here is the Python implementation of the above algorithm:

def lengthOfLIS(nums: List[int]) -> int:
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(0, i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

The time complexity of this solution is O(n^2) as we are looping through the input array twice. However, we can optimize this by using a binary search approach which can reduce the time complexity to O(nlogn).

1