Problem Link - Longest Increasing Subsequence

### Problem Statement

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in non-decreasing order. That is, it should be in increasing order, but we can have equal elements as well.

### Approach

The code uses a dynamic programming approach to find the length of the longest increasing subsequence. It initializes a `dp`

array where `dp[i]`

stores the length of the longest increasing subsequence ending at index `i`

. Starting from the second-to-last element, it checks all subsequent elements to see if they can extend the subsequence. If an element at index `j`

is greater than or equal to the element at index `i`

, it updates `dp[i]`

to be the maximum of its current value or `dp[j] + 1`

. Finally, the maximum value in the `dp`

array gives the length of the LIS.

### Time Complexity

O(n^2), where n is the number of elements in the array, due to the nested loops.

### Space Complexity

O(n), for storing the `dp`

array.