Cod sursa(job #2308285)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 26 decembrie 2018 19:34:26
Problema Subsir crescator maximal Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.86 kb
def read():
    with open('scmax.in', 'r') as fin:
        n = int(fin.readline())
        v = []
        for x in fin.readline().split(' '):
            v.append(int(x))
    return n, v


def main():
    n, v = read()
    s = [1] * n
    index = [0] * n
    for i in range(0, n):
        index[i] = i
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if v[i] < v[j] and s[i] < s[j] + 1:
                s[i] = s[j] + 1
                index[i] = j

    indexMaxim = 0
    maxS = 0
    for i in range(0, n):
        if maxS < s[i]:
            maxS = s[i]
            indexMaxim = i

    i = indexMaxim
    with open('scmax.out', 'w') as fout:
        fout.write(str(maxS) + '\n')
        while index[i] != i:
            fout.write(str(i + 1) + " ")
            i = index[i]
        fout.write(str(i + 1) + " ")


if __name__ == '__main__':
    main()