Competitive Programmer’s Handbook, Longest increasing subsequence - explanation needed

Question

I'm having hard time understanding a part of above mentioned topic.

Our ﬁrst problem is to ﬁnd the longest increasing subsequence in an array of n elements. This is a maximum-length sequence of array elements that goes from left to right, and each element in the sequence is larger than the previous element. For example, in the array

{6,2,5,1,7,4,8,3}

the longest increasing subsequence contains 4 elements:

2,5,7,8

Let length(k) denote the length of the longest increasing subsequence that endsatposition k. Thus,if we calculate all values of length(k) where 0≤k≤n−1, we will ﬁnd out the length of the longest increasing subsequence. For example, the values of the function for the above array are as follows:

length(0) = 1

length(1) = 1

length(2) = 2

length(3) = 1

ength(4) = 3

length(5) = 2

length(6) = 4

length(7) = 2

The part that i don't understand is why if for some k, length(k) = c then why is it possible for some n>k to have length(n)<length(k), the array that we choose does only extend in right direction, so I think the length(k) as k increases can't decrease because we are only getting new values What am I missing? Please help.

length[k] corresponds to the maximum length of a subsequence that ends at exactly position k, and not before. — Damien
So you mean that k-th element of an array has to be included in a sequence? — somerndguy
Not exactly. I mean that the sequences concerned by lenght[k] end at kth position — Damien

Selindek Selindek · Accepted Answer · 2020-09-27T10:50:32

Let length(k) denote the length of the longest increasing subsequence that ends at position k.

So, for example, length(3) = 1, because the value at that position is 1, so there are no any smaller numbers in the array to the left of it.

Competitive Programmer’s Handbook, Longest increasing subsequence - explanation needed

1 Answers