Solution For Longest Increasing Subsequence

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).

Step by Step Implementation For Longest Increasing Subsequence

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

/*
The idea is to maintain an array whose i^{th} element contains the length of the longest increasing subsequence that can be formed by considering the array elements up to the i^{th} element (including the i^{th} element).

For every new element nums[i], we iterate over all the previous elements nums[j] (where j < i) and find out the length of the longest increasing subsequence that can be formed by including the current element. We store this value in dp[i]. Finally, we return the maximum value in dp[].

Time complexity : O(n^2). Two loops of n are there.

Space complexity : O(n). dp array of size n is used.
*/

def lengthOfLIS(nums):
    
    # Base case - an empty list has a length of 0
    if not nums:
        return 0
    
    # Initialize an array to store the length of the longest
    # increasing subsequence at each index of the input list.
    # The first element is initialized to 1 since a list of 
    # length 1 is trivially an increasing subsequence.
    dp = [1] * len(nums)
    
    # Iterate over the input list, starting at index 1. For 
    # each element, iterate over the elements before it. If
    # the current element is greater than the element at j,
    # update dp[i] to be the maximum of dp[i] and dp[j] + 1.
    for i in range(1, len(nums)):
        for j in range(i):
            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.
    return max(dp)

var lengthOfLIS = function(nums) {
    // create an array to store length of longest subsequence at each index
    let dp = new Array(nums.length).fill(1);
    
    // iterate through each element in array
    for (let i = 0; i < nums.length; i++) {
        // iterate through each element before current element
        for (let j = 0; j < i; j++) {
            // if current element is greater than element at index j and length of subsequence at index j + 1 is greater than subsequence at index i
            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                // update length of subsequence at index i
                dp[i] = dp[j] + 1;
            }
        }
    }
    
    // return longest subsequence
    return Math.max(...dp);
};

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector dp(n, 1);
        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

public int LengthOfLIS(int[] nums) { // edge case if (nums.Length <= 1) { return nums.Length; } // create an array to track the length of the longest // increasing subsequence at each index int[] dp = new int[nums.Length]; // initialize the dp array to all 1's, // since the minimum length of an // increasing subsequence is 1 dp.Fill(1); // loop through the array, // starting at the second element for (int i = 1; i < nums.Length; i++) { // loop through the array, // up to the current index for (int j = 0; j < i; j++) { // check if the current element is greater than // the element at the previous index if (nums[i] > nums[j]) { // update the dp array at the current index // to be the maximum of the current value and // the value at the previous index + 1 dp[i] = Math.Max(dp[i], dp[j] + 1); } } } // return the maximum value in the dp array return dp.Max(); }