LeetCode #300: Longest Increasing Subsequence

LeetCode Solutions

https://leetcode.com/problems/longest-increasing-subsequence/description/

The idea of the solution is to use Dynamic Programming to solve this problem.

First, we create a dp array to store the length of the longest increasing subsequence up to each index.

For each index in the given array, we loop through all previous indices and check if the number at the current index is greater than the number at the previous index. If so, we update the dp array for the current index with the maximum value of the dp array up to the previous index plus 1.

Finally, we return the maximum value in the dp array as the length of the longest increasing subsequence.

Steps

  1. Initialize a dp array with all values set to 1, since every element in the array is itself a subsequence of length 1.
  2. Loop through the array from the second element to the end.
  3. For each index, loop through all previous indices from 0 to i-1.
  4. For each previous index j, check if nums[i] is greater than nums[j]. If so, update dp[i] to the maximum value of dp[i] and dp[j]+1.
  5. Return the maximum value in the dp array.

Here is the solution in python3:

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

Time and Space Complexity

The time complexity of this solution is O(n^2) since we have nested loops for each element in the array.

The space complexity is also O(n) since we are using a dp array to store the length of the longest increasing subsequence up to each index.