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;
}
``````
Copy The Code &

Input

cmd
nums = [10,9,2,5,3,7,101,18]

Output

cmd
4

#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;
}
};
``````
Copy The Code &

Input

cmd
nums = [10,9,2,5,3,7,101,18]

Output

cmd
4

#3 Code Example with Java Programming

```Code - Java Programming```

``````start coding.
class Solution {
public int lengthOfLIS(int[] nums) {
List subsequence = new ArrayList<>();
for (int i = 1; i  <  nums.length; i++) {
int currNum = nums[i];
if (currNum > subsequence.get(subsequence.size() - 1)) {
} else {
int idx = 0;
while (currNum > subsequence.get(idx)) {
idx++;
}
subsequence.set(idx, currNum);
}
}
return subsequence.size();
}
}
``````
Copy The Code &

Input

cmd
nums = [0,1,0,3,2,3]

Output

cmd
4

#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
};
``````
Copy The Code &

Input

cmd
nums = [0,1,0,3,2,3]

Output

cmd
4

#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
``````
Copy The Code &

Input

cmd
nums = [7,7,7,7,7,7,7]

Output

cmd
1

#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;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [7,7,7,7,7,7,7]

Output

cmd
1