Leetcode Longest Increasing Subsequence problem solution

YASH PAL,

In this Leetcode Longest Increasing Subsequence problem solution we have 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].

Leetcode Longest Increasing Subsequence problem solution

Problem solution in Python.

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

Problem solution in Java.

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

Problem solution in C++.

class Solution {
public:
    int dp[10000];
    int length(vector<int> &nums, int n){
        if(dp[n]!=-1)return dp[n];
        if(n==0)return dp[n]=0;
        int c=1;
        for(int i=n-1;i>0;i--){
            if(nums[n-1]>nums[i-1])
            {
                c=max(c,1+length(nums,i));
            }
        }
        return dp[n]=c;
    }
    int lengthOfLIS(vector<int>& nums) {
        memset(dp,-1,sizeof(dp));
        for(int i=nums.size();i>=0;i--)
            if(dp[i]==-1)
            length(nums,i);
        int ans=0;
        for(auto x:dp)
            ans=max(ans,x);
        return ans;
    }
};

Problem solution in C.

int lengthOfLIS(int* nums, int numsSize)
{
    if(numsSize == 0)
    {
        return 0;
    }
    int* array = (int*)malloc(sizeof(int) * numsSize);
    array[0] = nums[0];
    int LIS = 0;
    for(int i = 1; i < numsSize; ++i)
    {
        if(nums[i] > array[LIS])
        {
            array[LIS+1] = nums[i];
            LIS++;
        }
        else
        {
            for(int j = 0; j <= LIS; ++j)
            {
                if(array[j] >= nums[i])
                {
                    array[j] = nums[i];
                    break;
                }
            }
        }
    }

    return LIS + 1;
}

coding problems