Stack Overflow
Stack Overflow

Questions tagged [lis]

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics.

The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.

Reference.

120 questions
235
votes
21 answers

How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
Tony
  • 2,503
  • 4
  • 16
  • 7
40
votes
8 answers

longest increasing subsequence(O(nlogn))

LIS:wikipedia There is one thing that I can't understand: why is X[M[i]] a non-decreasing sequence?
outsiders
  • 431
  • 1
  • 5
  • 4
38
votes
7 answers

Find longest increasing sequence

You are given a sequence of numbers and you need to find a longest increasing subsequence from the given input(not necessary continuous). I found the link to this(Longest increasing subsequence on Wikipedia) but need more explanation. If anyone…
pappu
  • 431
  • 1
  • 6
  • 7
17
votes
5 answers

Number of all longest increasing subsequences

I'm practicing algorithms and one of my tasks is to count the number of all longest increasing sub-sequences for given 0 < n <= 10^6 numbers. Solution O(n^2) is not an option. I have already implemented finding a LIS and its length (LIS Algorithm),…
Wojciech Kulik
  • 7,823
  • 6
  • 41
  • 67
12
votes
5 answers

Longest chain of pairs

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c,d) can follow (a,b) if and only if b is less than c. Chains of pairs can be formed in this manner. Find the longest chain of pairs…
sww
  • 856
  • 1
  • 8
  • 15
7
votes
1 answer

Longest K Sequential Increasing Subsequences

Why I created a duplicate thread I created this thread after reading Longest increasing subsequence with K exceptions allowed. I realised that the person who was asking the question hadn't really understood the problem, because he was referring to a…
Ermolai
  • 303
  • 4
  • 15
7
votes
3 answers

1D Memoization in Recursive solution of Longest Increasing Subsequence

Calculating LIS (Longest Increasing Subsequence) in an array is a very famous Dynamic Programming problem. However in every tutorial they first show the recursive solution without using the concepts of DP and then solve it by applying Bottom-Up DP…
Shivang Bansal
  • 81
  • 1
  • 3
7
votes
7 answers

longest nondecreasing subsequence in O(nlgn)

I have the following algorithm which works well I tried explaining it here for myself http://nemo.la/?p=943 and it is explained here http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ as well and on stackoverflow…
user1781626
6
votes
1 answer

Number of Increasing Subsequences of length k

I am trying to understand the algorithm that gives me the number of increasing subsequences of length K in an array in time O(nklog(n)). I know how to solve this very same problem using the O(k*n^2) algorithm. I have looked up and found out this…
Andrés
  • 841
  • 2
  • 13
  • 31
4
votes
4 answers

How to use dynamic databases in Prolog?

I have written the following program, which calculates the longest non-decreasing sub-sequence of input array. The sub-program to find the longest list from the list of lists is taken from stackoverflow (How do I find the longest list in a list of…
UnSat
  • 1,347
  • 2
  • 14
  • 28
4
votes
1 answer

How to use a C struct in C++ code?

I am trying to write a program that should use a C library (the LIS library) in a C++ program. There seems to be a problem with the creation/initialization of struct objects. When I run the example program on the wikipediapage:…
DrDonut
  • 864
  • 14
  • 26
4
votes
2 answers

How does algorithm for Longest increasing subsequence [O(nlogn)] work?

I found algorithm mentioned in The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list): set st; set::iterator it; st.clear(); for(i=0; i
aamir
  • 3,753
  • 4
  • 23
  • 34
3
votes
1 answer

Longest Increasing and Decreasing subsequence (Top-Down with memoization)

Question - Given an array of integers, A of length N, find the length of longest subsequence which is first increasing then decreasing. Input:[1, 11, 2, 10, 4, 5, 2, 1] Output: 6 Explanation:[1 2 10 4 2 1] is the longest subsequence. I wrote a…
utkarsh bajpai
  • 33
  • 7
3
votes
1 answer

Find the LIS with the maximum sum

I have this code for finding the Longest Increasing Subsequence (LIS) but when i test my code I dont get maximum sum, for example: if I type 20 1 4 3 10 the answer is 1 3 10, but i need 1 4 10 This is my code in C: #include #include…
Oskar Moen
  • 41
  • 4
3
votes
1 answer

How to find longest increasing subsequence among all simple paths of an unweighted general graph?

Let G = (V, E) be an unweighted general graph in which every vertex v has a weight w(v). An increasing subsequence of a simple path p in G is a sequence of vertices of p in which the weights of all vertices along this sequence increase. The simple…
Chloe
  • 75
  • 6
1
2 3 4 5 6 7 8