🚀 Feature Request: Longest Increasing Subsequence (LIS) Algorithm

[770navyasharma]

Is your feature request related to a problem? Please describe.

I am looking for an efficient solution to the Longest Increasing Subsequence (LIS) problem. The task of finding the longest increasing subsequence in a given array is common in both competitive programming and real-world applications. Currently, this repository lacks a well-documented and optimized solution for this problem.

Describe the solution you'd like

I would like to contribute an optimized solution for finding the Longest Increasing Subsequence with the following two approaches:

1. O(n²) Dynamic Programming approach: Uses a 2D array or list to store the solutions of overlapping subproblems.
2. O(n log n) approach: Uses a combination of dynamic programming and binary search (or data structures like Fenwick Tree) to achieve better performance on larger inputs.

The solution should:

• Take an array of integers as input.
• Return the length of the longest increasing subsequence.
• Be well-documented with clear code comments and explanations.

Describe alternatives you've considered

Some alternatives that could be considered:

• A brute force approach that generates all possible subsequences and checks for the longest increasing subsequence, but this would have a very poor time complexity of O(2^n), making it unsuitable for large inputs.
• Using recursive solutions without memoization, but this would also lead to inefficiencies.

Additional context

The Longest Increasing Subsequence problem is a classic DP problem and is widely asked in coding interviews and used in various applications such as biology (e.g., DNA sequencing) and economics (e.g., stock market analysis). Adding this feature will make the repository more comprehensive for dynamic programming problems.

---

Would you like to work on this feature?

• Yes
• No
  @ajay-dhangar Please assign this issue to me

[github-actions]

👋 Hi @770navyasharma! Thanks for opening this issue. We appreciate your contribution to the Algo project. Our team will review it soon.