I’m working on a project where I need to find the longest increasing subsequence (LIS) from a given array of integers. However, the array can be quite large, so I’m looking for an efficient algorithm to solve this problem.

I’ve looked into dynamic programming solutions like the O(n^2) approach using an array to store the length of the LIS ending at each index, but I’m wondering if there’s a more efficient algorithm available.

Could someone please suggest an efficient algorithm or point me toward resources that discuss optimized approaches for finding the LIS?

Thank you in advance for your help!