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