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