# 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 trying to wrap my head around the different OPT Functions and the recurrence relation possible. The solutions I found always have some flaw in it. I will share the solutions I got below.

Here is the main question:

Given a sequence of numbers stored in an array A[1 . . . n] = ⟨a1, . . . , an⟩, compute a subsequence of A of maximum length (i.e., number of elements) whose elements are increasing

Our Usual Approach to LIS Problem is:

Let OPT(i) denote the length of the longest increasing subsequence of A that ends with ai.

Before the ending element, there is an element immediately before the ending element, i.e., the second to last element.

let aj be an element immediately before ai for an increasing subsequence, i.e., the subsequence ends with aj, ai

Recursive definition of OPT(i) will be:

OPT(i) = 1, if i = 1

OPT(i) = max {{1} ∪ {1 + OPT(j) | 1 ≤ j < i ∧ aj < ai}} otherwise


The answer to the input is: max{OPT(i) | 1 ≤ i ≤ n}

The new Approach that I have to take to solve this problem for Extra Credit:

A more ‘natural’ definition of OPT would be:

Let OPT(i) denote the length of the longest increasing subsequence within ⟨a1, . . . , ai

So for an Input Array A = [4, 5, 6, 1, 2] the OPT Array should be = [1,2,3,3,3].

I have tried using the following recurrence relations for OPT(i) to solving this problem:

1) First Attempt

OPT (1) = 1

For i > 1, let LIS_i be the set of all j where 1 ≤ j < i and aj < ai

If LIS_i is empty, then OPT(i) = 1.

Otherwise, OPT(i) = 1 + max{OPT (j) | for all j € LIS_i}


Feedback: Based on the recursive definition, OPT[4]=1 because no elements before 1 is smaller than 1. OPT[4] should be 3 because the longest increasing subsequence of <4, 5, 6, 1> is 4 5 6.

2) Second Attempt

OPT(i) = max{OPT(j) + 1 | 1 ≤ j < i ∧ aj < ai, OPT(i-1)}


Feedback: The OPT Array this recurrence relation generates is = [1,2,3,3,4].

I solved the previous problem of OPT[4] giving 1 by comparing the OPT value by previous element. But now there is a new problem I am facing.

I am getting the value for OPT[5] = 4 , which is wrong as there does not exist any LIS of length 4 in the given array.

This is because it is computing max{OPT[4]+1,OPT[4]}. When i = 5, and j=4 it considers that the LIS ends with 1(aj), which it incorrect.

OPT[4] gets its value to be 3 because A[4] which is 1 is not part of the LIS but the element before it (OPT[3]) has a larger OPT value which is 3. So it simply copies the largest value.

What I think is the correct approach is:

Our OPT(i) is the length of the longest increasing subsequence within ⟨a1, . . . , ai⟩. This does not necessarily mean that the LIS should be ⟨a1, . . . , ai⟩. It is within ⟨a1, . . . , ai⟩, so it could be ⟨a1, . . . , ai-1⟩, ⟨a1, . . . , ai-2⟩, so on.

I really need help solving this problem. Your feedback help will be appreciated.

Thanks!

• You should look up the $O(n \log (n))$ algorithm for LIS. You will realize that it uses $L[i][k] =$ increasing subsequence of $\langle a_1,...,a_i \rangle$ with length $k$ with the smallest possible last element and some placeholder if no such seq. exists . Using this your def. of OPT(i) becomes easy. Now you just need to find a recursion for $L$. Commented Mar 18, 2023 at 6:08