Length of longest increasing subsequence-Coding question asked by LinkedIn, Google, Goldmann Sachs

Placewit
2 min readJun 8, 2022

Problem Statement:

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

Input Format:

String S

Output Format:

String with order of vowels reversed

Sample Input 1:

[10,9,2,5,3,7,101,18]

Sample Output 1:

4

Sample input 2:

[0,1,0,3,2,3]

Sample output 2:

4

Sample Input 3:

[7,7,7,7,7,7,7]

Sample Output 3:

1

Constraint:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 10⁴

Approach:

To find the LIS for a given sequence nums, we need to return max(nums(i)).
The length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices before i. Therefore we can take a sequence of length of nums and solve iteratively where the element at index i be increased by 1 in each iteration.

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--