Find the longest nondecreasing subsequence


#1

Hi:

I have a tiny question on the codes of question 16.12 (python version), find the longest nondecreasing subsequence.

The assignment in the for loop reads:
max_length[i] = max(1 + max( max_length[j] for j in range(i) if A[i] >= A[j]), default = 0), max_length[i])

I don’t understand why you need to find the max of 1+max(…) and max_length[i], since max_length[i] was initiated to 1, which can’t be larger than 1+max(…).

So why can’t I write this line as:

max_length[i] = 1 + max( max_length[j] for j in range(i) if A[i] >= A[j]), default = 0)?

Thanks.


#2