Lost in the nlogn algo of 17.21 longest nondecreasing subsequence in 1.4.7

#1

My questions is for the nlogn algorithm, NOT the DP algorithm.

(1)
the book says “it is a greedy algorithm and uses binary search”, but I didn’t find the explanation for what part it is greedy. Where do you prove that it has one of the important greedy property : optimal substructure.?

(2)
In the description it says “If no length j+1 nondecreasing subsequence exists in A[0], A[1], … A[i], then Mi+1,j+1 must be A[i+1]”.

How come there would be a chance that there is a length j+1 nondecreasing subsequence exist in A[0], A[1], … A[i] in the first place? You already said that “look for the largest j such that Mi,j<=A[i+1]”, it means j is already largest, why you are assuming there could be a j+1 nondecreasing subsequence inside A[0],A[1]…A[i]?

(3) You use vector tail_values to represent Mi,j, why the answer finally returns size of the vector? I am kind of completely lost on the how you map your description to the data structure and the meaning of the data structure that you are using.

In fact, I have too many questions on this solution mainly because I don’t understand this nlogn algorithm at all. Would you please elaborate it more?

0 Likes
#2

Hey Pete,

The nlogn algorithm is a hard one, and let me briefly explain your questions here:

  1. IMO, the optimal substructure in this problem lies in the Mi,j array where for a given i value, if j1 > j2, Mi,j1 >= Mi,j2. This property is also very important for the binary search algorithm to work.

  2. In our solution, we overlap the meaning of M. Let’s think back the meaning of M which wants to store the smallest tail value of each length j nondecreasing sequence. Why we want to the smallest one? Because it provide most potential for the future to expand to j + 1 nondecreasing sequence. This is also part of the reason why we call it is a greedy algorithm because each value of M maximize the potential to extend.

  3. In fact, the size of tail_values represents the largest j you can achieve which also means the size of the longest nondecreasing sequence.

We are going through a major solution rewrite and hopefully by the time we rewrite this part, your questions and my answers will be the foundation to generate a better explanation for this algorithm.

0 Likes
#3

Hi TH,

Generally, at a very high level, I understand the algorithm. But the wording really makes it confusing.

Still I am holding suspicion on the redundancy of the problem I mentioned in No.2 above.

Could we replace the text

“When processing A[i+1], we look for the largest j such that Mi,j<=A[i+1]. First, assume such a j exists. Then we can construct a j + 1 length subsequence that ends at A[i+1]. If no length j+1 nondecreasing subsequence exists in A[0], A[1], … A[i], then Mi+1,j+1 must be A[i+1], otherwise it remains equal to Mi,j+1. Furthermore, Mi+1,j’ remains unchanged for all j’ <=j”

with

“When processing A[i+1], we look for the largest j such that Mi,j<=A[i+1]. First, assume such a j exists, denote it as jm. Then we can construct a jm + 1 length subsequence that ends at A[i+1], which means Mi+1,jm+1 is A[i+1]. Furthermore, Mi+1,j’ remains unchanged for all j’ <=jm”

Do you think this suffices the description? Or do you think it will miss some corner case examples where I suggests deleting?

0 Likes
#4

Hey Pete,

Thanks for your reply, and I think what you are saying matches the idea we want to present. From now, it is fine to replace this with that, and I will update you once we finish the rewriting of this part. Thanks.

0 Likes