**Problem**

Given an integer array `arr`

, return the length of the longest **strictly increasing** subsequence. Strictly increasing sequence is a sequence such that all elements of the sequence are sorted in increasing order.

**NOTE**: In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence {A, B, D} is a subsequence of {A, B, C, D, E, F} obtained after removal of elements C, E and F.

**Example 1:**

Input:`arr`

= [10, 9, 2, 5, 3, 7, 101, 18]Output:4Explanation:The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

This problem could be **solved by Dynamic programming in O(n ^{2}) time complexity and O(n) auxiliary space.**

###### Optimal Substructure

An optimal solution to problem contain optimal solution to subproblems. To consider all subsequence of array elements, **2 cases for every element arises:**

- Element is included in optimal set
- Element is not included in optimal set

Therefore, longest subsequence obtained from n items is maximum of the following:

- Longest subsequence obtained by n-1 elements, excluding nth element.
- nth element + longest subsequence obtained by n-1 elements

Then, LIS(i) can be recursively written as:

if LIS[i] < LIS[j] + 1 LIS(i) = 1 + LIS[j] where 0 < j < i and arr[j] < arr[i]; else LIS(i) = 1, if no such j exists. ans = MAX(ans, LIS[i])

**Code Implementation**

```
//
// main.cpp
// Longest Increasing Subsequence (LIS)
//
// Created by Himanshu on 17/09/21.
//
#include <iostream>
using namespace std;
const int N = 8;
void LIS (int A[]) {
int LIS[N], sol = 1;
for (int i=0; i<N; i++) {
LIS[i] = 1;
for (int j=0; j<i; j++) {
if (A[i] > A[j] && LIS[i] < LIS[j]+1) {
LIS[i] = LIS[j] + 1;
}
}
sol = max(sol, LIS[i]);
}
cout<<"Length of Longest Increasing Subsequence (LIS) is: "<<sol<<endl;
}
int main() {
int A[N] = {10, 9, 2, 5, 3, 7, 101, 18};
LIS(A);
}
```

**Output:**

Length of Longest Increasing Subsequence (LIS) is: 4

Here’s a working example: Ideone