300. Longest Increasing Subsequence – Leetcode Solutions

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

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        # Initialize dp array where dp[i] means the length of LIS ending at index i
        dp = [1] * len(nums)
        
        # Iterate over the array to fill the dp array
        for i in range(1, len(nums)):
            for j in range(i):
                # If nums[i] can extend the sequence ending at nums[j]
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        # The result is the maximum value in the dp array
        return max(dp)

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // Edge case: If nums is empty, return 0
        if (nums.empty()) {
            return 0;
        }
        
        // dp[i] will store the length of the longest increasing subsequence ending at index i
        vector<int> dp(nums.size(), 1); // Initialize dp array with 1's
        
        // Iterate over the nums array to populate the dp array
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                // If nums[i] can extend the sequence ending at nums[j]
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        
        // The length of the longest increasing subsequence is the maximum value in dp array
        return *max_element(dp.begin(), dp.end());
    }
};

var lengthOfLIS = function(nums) {
    // Edge case: if nums is empty, return 0
    if (nums.length === 0) {
        return 0;
    }

    // Initialize dp array where dp[i] is the length of the longest increasing subsequence ending at index i
    let dp = new Array(nums.length).fill(1);

    // Iterate through the array to populate the dp array
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // If nums[i] can extend the subsequence ending at nums[j]
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    // The length of the longest increasing subsequence is the maximum value in the dp array
    return Math.max(...dp);
};

class Solution {
    public int lengthOfLIS(int[] nums) {
        // Edge case: if the array is empty, return 0
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // Initialize a dp array where dp[i] represents the length of the LIS ending at index i
        int[] dp = new int[nums.length];
        
        // Initially, the LIS ending at each index is just the element itself, so dp[i] = 1
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }

        // Iterate through the array to populate the dp array
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // If nums[i] is greater than nums[j], it can extend the sequence ending at nums[j]
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // Find the maximum value in the dp array, which is the length of the LIS
        int maxLength = 0;
        for (int i = 0; i < dp.length; i++) {
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}