CODEWITHSUNDEEP
algorithmdynamic-programming
Hiresh
Hiresh

Reputation: 89

Unable to understand algorithm for Longest Increasing Sub-sequence

I have been through many online resources to understand how the problem has the optimal sub-structure, but all in vain, I am unable to comprehend how the solution is obtained by solving smaller sub-problems in this case.

I would be thankful if any explanation helps in understanding the solution.

so far, I understand the optimal sub-structure property as follows:

Example Factorial:

So for a factorial of 40 ,fact(40), we can achieve the solution by calculating fact(39)*40, and so on for 39,38....2 ans as we know that fact(2) is 2 we can build it up from 2 to 40 in the same way.

But I am not able to relate in terms of LIS, please help

A full explanation of the solution would be nice, excluding the overlapping subproblems issue, as that can be handled later on.

Thanks.

Upvotes: 1

Views: 634

Answers (2)

Maja Kudlicka
Maja Kudlicka

Reputation: 31

LIS for the sequence (problem) can be solved by using LIS for the smaller sequences (sub-problem)and that's why it is known to have the optimal sub-structure.

Let me try to explain how this works with the example. Let's take a random sequence of 10 numbers:

[21, 24, 13, 48, -3, 41, 36, 8, -10, 22]

We will use smaller problems (smaller sequence) to solve this problem. The definition of the subproblem is this case is 'What is the longest increasing sequence of numbers that ends at a given element?'

It is important to understand that this subproblem is NOT the same as LIS- the subproblem has a stricter definition that the original problem (LIS doesn't need to end at the last element).

For readability purposes, I'll call the 'longest increasing subsequence that ends at given element': LIS*.

The relationship between LIS* and LIS is that LIS takes Max of LIS*

Let's start with just one number.

[21]

What is the longest increasing subsequence that ends at 21? It is simply '21'. Therefore the length of our sequence is 1.

Sequence: [21]
LIS*: 1
LIS: 1

Now, for the second element (24), according to the definition, we need to use the solution for the problem we already solved. We will use LIS for the first element, check whether second element is bigger (a[i] > a[j) and whether LIS[j]+1 > LIS[i]. The longest increasing sequence that ends at 24 is '21, 24' and has the length of 2.

Sequence: [21, 24]
LIS*: 2
LIS: 2

Let's take 3rd element (13). What is the longest increasing subsequence that ends at 13? Well, 13 is smaller than 21 and smaller than 24 so the condition a[i] > a[j] is not fulfilled for any of the previous elements.The longest increasing subsequence that ends at 13 is therefore just '13' and has the length of 1. LIS for sequence 21,24,13 is still 2.

Sequence: [21, 24, 13]
LIS*: 1
LIS: 2

Let's look at 4th element (48). We know that the solution for the 3-length sequence was 2. We can find previous element (24) that fulfils criteria a[i] > a[j] and LIS[j]+1 > LIS[i]. We know that solution for the previous element (smaller problem) was 2, therefore the solution here will be 2+1=3.

Sequence: [21, 24, 13, 48]
LIS*: 3
LIS: 3

We repeat the logic for all subsequent elements.

Sequence: [21, 24, 13, 48, -3, 41, 36, 8, -10, 22]
LIS*:            1    2    1    3    1    3    3    2    1    3
LIS:             1    2    2    3    3    3    3    3    3    3

As you can see, the solution to the original problem (long sequence) can be obtained by looking at sub-problem (smaller sequences) and therefore this problem is known to have the optimal sub-structure.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726579

Before considering optimal substructure, you need to decide what are subproblems in the case of LIS. Let's use this definition:

In an array a[N] of length N a subproblem LIS[k] is to find the length of a longest increasing subsequence from the initial index, which ends precisely at the element a[k].

It is important to understand the difference here: LIS[k] is not a solution to LIS on the first k elements; that would be Max(LIS[i]) for all is up to k. It is the length of the longest increasing subsequence that ends at the particular element.

With this definition in hand, it is easy to construct a solution to LIS:

  • For each i up to N:
  • Set LIS[i] to 1 (in the worst case, a number is a subsequence of one)
  • Search LIS[j] from the initial element up to i-1, inclusive, for js such that a[i] > a[j], and LIS[j]+1 > LIS[i].

It is easy to see that the above algorithm constructs a solution to LIS[i] given solutions to subproblems LIS[j] for all js below i in O(i). Since we can construct a solution to a k problem from solutions to k-1 sub-problems, the problem has optimal substructure.

Note: The above can be further optimized by using binary search. The reasoning about subproblem and optimal substructure remains the same, though.

Upvotes: 0

Related Questions