TheAlgorithms/Go

Optimized nlogn approach for longest increasing sub-sequence

anirudnits opened this issue · 2 comments

anirudnits commented

Description
The dynamic programming approach for finding the longest increasing sub-sequence in O(n^2) within an integer array is defined here: https://github.com/TheAlgorithms/Go/blob/master/dynamic/longestincreasingsubsequence.go. However, there's a greedy approach which solves the problem in O(nlogn).

For enhancement:

  • Greedy logic for finding the longest increasing sub-sequence in lesser asymptotic time.
tjgurwara99 commented

I don't think you need to open issues when you're thinking of adding an algorithm to the repository. Just open a PR and the maintainers will take a look.

  • 👍1
siriak commented

On the other hand, it gives a leg up to other folks who might be interested in contributing, doesn't it? There's nothing wrong with having a backlog of up-for-grabs issues IMO.

  • 👍4