Skip to main content

Questions tagged [longest-increasing-subsequence]

Filter by
Sorted by
Tagged with
1 vote
1 answer
48 views

Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
1 vote
1 answer
253 views

Longest Increasing Co-Prime Subsequence?

This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways. Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing ...
2 votes
0 answers
118 views

Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
-1 votes
2 answers
416 views

Longest increasing subsequence when a number can be added to all numbers in a subarray

A sequence $(a_1,a_2, \dots, a_n) $ and natural numbers $n$ and $k$ are given. We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...