Cod sursa(job #2308546)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 27 decembrie 2018 12:43:18
Problema Subsir crescator maximal Scor 30
Compilator py Status done
Runda Arhiva educationala Marime 1.01 kb
import sys


def read():
    with open('scmax.in', 'r') as fin:
        n = int(fin.readline())
        v = []
        line = fin.read()
        for x in line.split(" "):
            if x.isdigit():
                v.append(int(x))
    return n, v


def main():
    n, v = read()
    s = [1] * n
    index = [0] * n
    i = 0
    while i < n:
        index[i] = i
        i += 1

    i = n - 2
    while i >= 0:
        j = i + 1
        while j < n:
            if v[i] < v[j] and s[i] < s[j] + 1:
                s[i] = s[j] + 1
                index[i] = j
            j += 1
        i -= 1

    index_maxim = 0
    max_s = 0
    i = 0
    while i < n:
        if max_s < s[i]:
            max_s = s[i]
            index_maxim = i
        i += 1

    i = index_maxim
    with open('scmax.out', 'w') as fout:
        fout.write(str(max_s) + '\n')
        while index[i] != i:
            fout.write(str(v[i]) + " ")
            i = index[i]
        fout.write(str(v[i]) + " ")
    sys.exit(0)


if __name__ == '__main__':
    main()