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.