Cod sursa(job #2542011)

Utilizator urtiComanac Dragos urti Data 9 februarie 2020 12:32:20
Problema Subsir crescator maximal Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.98 kb
fin = open("scmax.in", "r")
fout = open("scmax.out", "w")
lines = fin.readlines()
arr = lines[1].split()
#arr = [2, 12, 3, 6, 14, 3 ,4, 7,2] # --->  12 6 4 2
for i in range(len(arr)):
    arr[i] = int(arr[i])

def LDS (arr):
    v = []
    daddys = [-1]
    v.append(1)
    i = 1

    while i < len(arr):


        mx_len = 0
        mx_daddy = -1
        for j in range(0, i):
            if arr[j] < arr[i] and mx_len < v[j]:
                mx_len = v[j]
                mx_daddy = j

        v.append(mx_len+1)
        daddys.append(mx_daddy)

        i += 1
    mx = v[0]
    mx_poz = 0
    for i in range(1,len(arr)):
        if mx < v[i]:
            mx = v[i]
            mx_poz = i

    poz = mx_poz
    seq = []
    while poz != -1:
        seq.append(arr[poz])
        poz = daddys[poz]

    seq.reverse()
    fout.write(str(len(seq)) + "\n")
    s = ""
    for i in seq:
        s += str(i)
        s += " "
    fout.write(s)

LDS(arr)