# 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 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.

• 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? Commented Dec 28, 2022 at 18:59
• 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
– Hjm
Commented Dec 29, 2022 at 8:54
• 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? Commented Dec 29, 2022 at 17:12
• @LogicalX they are natural numbers. And I would like an algorithm that runs in polynomial time
– Hjm
Commented Dec 30, 2022 at 8:40

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.

• 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.
– Hjm
Commented Jan 1, 2023 at 9:48
• ...then what's the point of x? you need to be much clearer with your question if you want a clear answer. Commented Jan 1, 2023 at 15:37
• 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.
– Hjm
Commented Jan 1, 2023 at 16:37
• Ok, I think I understand now. I'll edit my solution to work for your problem. Commented Jan 1, 2023 at 16:49
• Should answer the question now. Tell me if this helps. Commented Jan 1, 2023 at 18:18

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
• 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

$$dp[e][x][\text{added"}]=1 + \max(\max_{d

$$dp[e][x][\text{after"}]=1 + \max(\max_{d

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.

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