Leetcode Longest Increasing Subsequence problem solution

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

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;
}