Longest Increasing Subsequence LeetCode Solution | Easy Approach

Longest Increasing Subsequence 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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Longest Increasing Subsequence Solutions

✅Time: O(n)
✅Space: O(n)

C++

class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    if (nums.empty())
      return 0;

    // dp[i] := length of LIS ending at nums[i]
    vector<int> dp(nums.size(), 1);

    for (int i = 1; i < nums.size(); ++i)
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i])
          dp[i] = max(dp[i], dp[j] + 1);

    return *max_element(begin(dp), end(dp));
  }
};

Java

 
class Solution {
  public int lengthOfLIS(int[] nums) {
    if (nums.length == 0)
      return 0;

    // dp[i] := length of LIS ending at nums[i]
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);

    for (int i = 1; i < nums.length; ++i)
      for (int j = 0; j < i; ++j)
        if (nums[j] < nums[i])
          dp[i] = Math.max(dp[i], dp[j] + 1);

    return Arrays.stream(dp).max().getAsInt();
  }
}

Python

 class Solution:
  def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums:
      return 0

    # dp[i] := LIS ending at nums[i]
    dp = [1] * len(nums)

    for i in range(1, len(nums)):
      for j in range(i):
        if nums[j] < nums[i]:
          dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Watch Tutorial

Checkout more Solutions here