Python.Write a function longest_increasing_subsequence(scores) which takes a lis

Question

Python.Write a function longest_increasing_subsequence(scores) which takes a list of scores, and returns the longest (strictly) increasing subsequence of those scores. Write it in a bottom-up manner (because the Python recursion stack is limited). Note that, assuming your subproblems from part only find the size of the best result, you should also keep parent pointers so that you can reconstruct the actual subsequence.

You work on your thesis over the weekend, and every time you make a change to your code, you run your test-awesomeness.py script, which spits out a score telling you how awesome your code is. During two hard days of work, you accumulate a large, time- ordered list of these awesomeness scores, e.g., [32, 31, 46, 36, 32, 36, 30, 33, 22, 38, 2, 13 You have a weekly meeting with your advisor, and each week you have to show that you made progress, so that he'll leave you alone for another week. You devise a plan in which every week you will show your advisor a newer version of your code, along with an awesomeness score that is better than the previous week's. To maximize the number of weeks of slacking you get out of your two days of work, you need to calculate a longest increasing subsequence of your awesomeness scores. In the example, one such subsequence would be 31, 32, 36, 38]. The subsequence should be strictly increasing, because you need to show improvement each time. Thinking back to your Introduction to Algorithms days, you have a vague recollection that longest increasing subsequence is one of those problems that can be solved by Dynamic Programming

Explanation / Answer

*** Source Code ***

def longest_increasing_subsequence(score):

    if not score:

        return score

    M = [None] * len(score)    # store an index of seq

    P = [None] * len(score)    # point to M

    # marks the length of longest incresing subsequence found up

    L = 1

    M[0] = 0

    # Looping over the sequence starting from the second element

    for i in range(1, len(score)):

       

        # hence we want the lower bound at the end of the search process.

        lower = 0

        upper = L

        # binary search will not look at the upper bound value,

        # So we'll have to check that manually

        if score[M[upper-1]] < score[i]:

            j = upper

        else:

            # binary search loop

            while upper - lower > 1:

                mid = (upper + lower) // 2

                if score[M[mid-1]] < score[i]:

                    lower = mid

                else:

                    upper = mid

            j = lower  

        P[i] = M[j-1]

        if j == L or score[i] < score[M[j]]:

            M[j] = i

            L = max(L, j+1)

    # Building the result

    result = []

    pos = M[L-1]

    for _ in range(L):

        result.append(score[pos])

        pos = P[pos]

    return result[::-1]    # reversing the result

score = [32 , 31 , 46 , 36 , 32 , 36 , 30 , 33, 22, 38, 2, 13]

print (longest_increasing_subsequence(score))

*** OUTPUT ***

Score = [32 , 31 , 46 , 36 , 32 , 36 , 30 , 33, 22, 38, 2, 13]

result = [31, 32, 33, 38]

Score = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60]

result = [10, 22, 33, 41, 60]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.