Algorithm
Problem Name: 300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence (A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.)
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
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 10
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int lower_bound(int *p, int start, int end, int k) {
int mid;
if (start > end) {
return start;
}
mid = start + (end - start) / 2;
if (p[mid] == k) return mid;
if (p[mid] > k) return lower_bound(p, start, mid - 1, k);
return lower_bound(p, mid + 1, end, k);
}
int lengthOfLIS(int* nums, int numsSize) {
int *lens, max, i, j;
if (numsSize == 0) return 0;
lens = malloc(numsSize * sizeof(int));
//assert(lens);
max = 1;
#if 0 // O(n^2) 19ms
for (i = 0; i < numsSize; i ++) {
lens[i] = 1; // starts from 1
for (j = 0; j < i; j ++) {
if (nums[i] > nums[j] && // a small number is ahead
lens[i] < lens[j] + 1) { //
lens[i] = lens[j] + 1; // increase 1
}
}
if (max < lens[i]) max = lens[i];
}
#else // O(nlogn) 3ms
int last = 0;
int *p = lens; // p is array of sorted numbers
// initialize p with the first num
p[0] = nums[0];
// for the rest of nums
for (i = 1; i < numsSize; i ++) {
// find proper location of num in sorted array p
j = lower_bound(p, 0, last, nums[i]);
// save it in p
p[j] = nums[i];
if (last < j) last = j;
}
max = last + 1; // the length of final p is the answer
#endif
free(lens);
return max;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int maxlen = 0;
vector<int>dp(nums.size(), 1);
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < i; j++)
if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
maxlen = max(maxlen, dp[i]>;
}
return maxlen;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
start coding.
class Solution {
public int lengthOfLIS(int[] nums) {
List subsequence = new ArrayList<>();
subsequence.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
int currNum = nums[i];
if (currNum > subsequence.get(subsequence.size() - 1)) {
subsequence.add(currNum);
} else {
int idx = 0;
while (currNum > subsequence.get(idx)) {
idx++;
}
subsequence.set(idx, currNum);
}
}
return subsequence.size();
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const lengthOfLIS = function(nums) {
const stack = []
for(let e of nums) {
if(stack.length === 0 || e > stack[stack.length - 1]) {
stack.push(e)
continue
}
let l = 0, r = stack.length - 1, mid
while(l < r) {
const mid = l + ((r - l) >> 1>
if(e > stack[mid]) l = mid + 1
else r = mid
}
stack[l] = e
}
return stack.length
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i + j) // 2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0300_LongestIncreasingSubsequence
{
public int LengthOfLIS(int[] nums)
{
if (nums.Length == 0) return 0;
int[] dp = new int[nums.Length];
int length = 0;
foreach (int num in nums)
{
int i = Array.BinarySearch(dp, 0, length, num);
if (i < 0) i = ~i;
dp[i] = num;
if (i == length) length++;
}
return length;
}
}
}
Input
Output