-1
$\begingroup$

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 exist an interval of pointers $[l, r]$ and an integer $x$, $-k\le x\le k$, such that $b_i = a_i + x$ for $i \in [l, r]$, and $b_i = a_i$ for $i \notin [l, r]$.

Input: The natural numbers $n$, $k$ and the sequence $a$.

Output: The longest increasing subsequence that can be created through a sequence $b$.

I want to find a polynomial-time algorithm that solves this problem

I know how to find longest increasing subsequence in general.

I think we'll have to use Dynamic Programming.

$\endgroup$
4
  • 1
    $\begingroup$ Is x constant for all b_i? Is the array of b given, or is that what we're trying to find? This question needs to be clarified a lot. What exactly is it that we're looking to solve? $\endgroup$
    – LogicalX
    Commented Dec 28, 2022 at 18:59
  • $\begingroup$ x is constant for all $b_i $ with $i \in [l, r]$. We want to find the longest increasing subsequence that can be created from the sequences b $\endgroup$
    – Hjm
    Commented Dec 29, 2022 at 8:54
  • $\begingroup$ What are the constraints for n and k? Are you looking for an answer that runs in a certain time complexity, or is a brute force solution ok? $\endgroup$
    – LogicalX
    Commented Dec 29, 2022 at 17:12
  • $\begingroup$ @LogicalX they are natural numbers. And I would like an algorithm that runs in polynomial time $\endgroup$
    – Hjm
    Commented Dec 30, 2022 at 8:40

2 Answers 2

0
$\begingroup$

Here's a simple solution that runs in O(n) time. To explain the solution, we must make a few observations.

First, note that having a negative value of x has the same effect as a positive value (ex. having x = -3 will produce a sequence b with the same longest increasing subsequence as x = 3) so we should only test positive values of x.

Given this, also note that it will never be sub-optimal to have the interval [l, r] be at the end of an increasing subsequence, as any optimal solution without [l, r] at the end can be turned into another optimal solution by simply extending [l, r] to go all the way to the end of the subsequence. It can be proved that extending [l, r] to the right will never make an increasing subsequence worse.

Thus, a naive solution would be to simply go through all possible optimal values of l for each possible value of x. This would give us an O(nk) algorithm. However, we can realize that all optimal solutions with [l, r] starting at a fixed l, another optimal solution can be made by simply increasing the value of x; the only purpose of the interval [l, r] is to 'fix' the step between a[l-1] and a[l] in order to maintain an increasing subsequence. Therefore, it is always optimal to set x to the highest value possible -- in this case, k. This removes the need to loop through all values of x an allows for a solution in O(n) time.

Pseudocode:

Keep an integer "sl" to store the index of l that gives the current LIS
Keep an integer "sr" to store the length of the current LIS, initialized to 0
Keep an integer "tl" to store the current index of l
Keep an integer "tr" to store the current length if l were to be at tl, initialized to 0
Keep a boolean "used" to remember whether we've used the a[i]+x rule yet
For each value of i from 0 to n-2:
    If (not used) and (a[i+1] <= a[i]) and (a[i+1]+x > a[i]):
        tl = i+1
        tr++
        used = true
    Else if (used) and (a[i+1] > a[i]):
        tr++
    Else:
        If (tr > sr):
            sr = tr
            sl = tl
        used = false
        tr = 1
If (tr > sr):
    sl = tl

Keep an array "b" of size n, initialized to be the same as the given array a
For each value of i from sl to n-1:
    b[i] += k
return b

This algorithm is O(n) because it runs one loop through all the items a, which is n items.

Cheers.

$\endgroup$
6
  • $\begingroup$ But the $b$ sequence is not given. You want to create the b sequence with longest increasing subsequence and calculate the longest increasing subsequence as well. $\endgroup$
    – Hjm
    Commented Jan 1, 2023 at 9:48
  • 1
    $\begingroup$ ...then what's the point of x? you need to be much clearer with your question if you want a clear answer. $\endgroup$
    – LogicalX
    Commented Jan 1, 2023 at 15:37
  • $\begingroup$ Sorry for the confusion. Our inputs are the two natural numbers n, k and the sequence a. Our output should be the longest increasing subsequence that can be created through a sequence b. The variable x (probably because I obviously don't know the answer to the question) is used to describe the sequences b and their relation to the sequence a. $\endgroup$
    – Hjm
    Commented Jan 1, 2023 at 16:37
  • $\begingroup$ Ok, I think I understand now. I'll edit my solution to work for your problem. $\endgroup$
    – LogicalX
    Commented Jan 1, 2023 at 16:49
  • $\begingroup$ Should answer the question now. Tell me if this helps. $\endgroup$
    – LogicalX
    Commented Jan 1, 2023 at 18:18
0
$\begingroup$

All indices below are understood to take valid values.

As expected, we will use dynamic programming.

Consider an increasing subsequence of $$a_1,\cdots a_{l-1}, a_l+x, a_{l+1}+x, \cdots, a_r+x, a_{r+1}, \cdots, a_n$$ that ends at element $a_e$ or $a_e+x$.

Classify that subsequence

  • by $(e, 0,``\text{before"})$ if $e<l$
  • by $(e, x,``\text{added"})$ if $l\le e\le r$
  • by $(e, x,``\text{after"})$ if $e>r$ and that sequence contains at least one element of the form $a_i+x$.

Let $dp[e][x][stage]$ be the length of the longest sequence that is classified by $(e, x, stage)$, where $1\le e\le n$, $-k\le x\le k$, $stage$ is one of $``\text{before"}$, $``\text{added"}$ and $``\text{after"}$.

What we are asked to compute is the maximum of all $dp[e][x][stage]$.

We have the following recurrence relations: (function $\max$ takes value $0$ if its arguments turn out to be empty)

$$dp[e][0][``\text{before"}]=1 + \max_{d<e\text{ and }a_d<a_e}dp[d][0][``\text{before"}]$$

$$dp[e][x][``\text{added"}]=1 + \max(\max_{d<e\text{ and }a_d<a_e+x}dp[d][0][``\text{before"}],\ \max_{d<e\text{ and }a_d<a_e}dp[d][x][``\text{added"}])$$

$$dp[e][x][``\text{after"}]=1 + \max(\max_{d<e\text{ and }a_d+x<a_e}dp[d][x][``\text{added"}],\ \max_{d<e\text{ and }a_d<a_e}dp[d][x][``\text{after"}])$$

The first recurrence relation is, in fact, (one of) the usual recurrence relation that is used to compute the longest increasing subsequence of a sequence.

The base cases are $dp[1][0][``\text{before"}]=dp[1][x][``\text{added"}]=dp[1][x][``\text{after"}]=1$ for all $x$.

(By the way, $dp[e][0][``\text{before"}]=dp[e][0][``\text{added"}]$ for all $e$. So we can remove stage $``\text{before"}$.)

The time-complexity is $O(kn^2)$ since, basically, there are $O(nk)$ entries to compute and it takes $O(n)$ to compute each entry.


If we adapt the $O(n\log n)$-time algorithm for the usual longest subsequence problem, we will have a $O(kn\log n)$ algorithm.

$\endgroup$
3
  • $\begingroup$ Can we do any changes so the complexity doesn't include k? $\endgroup$
    – Hjm
    Commented Jan 5, 2023 at 20:16
  • $\begingroup$ @Hjm Yes. Are you interested in $O(n^3\log n)$ time? $\endgroup$
    – John L.
    Commented Jan 5, 2023 at 20:43
  • $\begingroup$ Yes, if you can tell me how to achieve it $\endgroup$
    – Hjm
    Commented Jan 8, 2023 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.