Longest Increasing Subsequence Coding Question-Asked in Google Interviews

Problem Statement :

Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array.

Input Format:

The first line of the input contains an integer ’N’, denoting the total number of elements of the array.

The second line of the input contains the array elements of array A.

Output Format:

The output consists of one line containing the length of the largest increasing subsequence.

Given:

6
5 8 3 7 9 1

Output:

3

Explanation of given Test Cases :

Longest increasing subsequence
5 7 9, with length 3.

Approach:

Create an array of N length where ith value will be the last value for a subsequence of length (i+1).

Iterate over the array, use binary search to find best indexes to place new elements in the dp array.

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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Crossplatform Input Controller made Easy!

Master regex hands-on

Regex example

101 — Dashboards with Python — Pt.1

[Leetcode] Single Number

Deploy Latest Pandas Library in Lambda Lambda Layer

Kotlin for Android development — coming from Swift

[Leetcode] Heap

Introducing TooTanium, an Applications For Worker 4.0

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Jelly Beans Jars Puzzle

Top K Frequent Elements

Leetcode 2226. Maximum Candies Allocated to K Children

Meta / Amazon / Google / Microsoft Interview Question: Wildcard Matching Solution | LeetCode-44…