Find the longest nondecreasing subsequence

**helloworld** · May 21, 2018, 8:08am

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.

**tsunghsienlee** · May 21, 2018, 5:55pm

github.com

adnanaziz/EPIJudge/blob/master/epi_judge_python_solutions/longest_nondecreasing_subsequence.py

from test_framework import generic_test


def longest_nondecreasing_subsequence_length(A):

    # max_length[i] holds the length of the longest nondecreasing subsequence
    # of A[:i + 1].
    max_length = [1] * len(A)
    for i in range(1, len(A)):
        max_length[i] = 1 + max(
            (max_length[j] for j in range(i) if A[i] >= A[j]), default=0)
    return max(max_length)


if __name__ == '__main__':
    exit(
        generic_test.generic_test_main(
            "longest_nondecreasing_subsequence.py",
            'longest_nondecreasing_subsequence.tsv',
            longest_nondecreasing_subsequence_length))