Subsequência Crescente Mais Longa com Soma Máxima
Dado um array de
n inteiros, pretende-se encontrar a subsequência crescente mais longa do array. Se existirem várias subsequências com este comprimento, pode ser devolvida qualquer uma delas.Uma subsequência de um array obtém-se removendo alguns (possivelmente nenhuns) elementos do array, sem alterar a ordem dos elementos que restam. Por exemplo, se o array for , então é uma subsequência de , mas não o é, pois a ordem dos elementos não é preservada.
💡
Uma subsequência crescente de um array é uma subsequência em que os elementos estão em ordem crescente. Por exemplo, se o array for , então é uma subsequência crescente de , mas não o é, porque os elementos não estão em ordem crescente.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 1000), que representa o tamanho do array.A segunda linha contém
n inteiros separados por espaço (), representando os elementos do array.Saída
O programa deve imprimir a soma da subsequência crescente mais longa que tenha a soma máxima.
Entrada | Saída |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Explicação
- No primeiro exemplo, a subsequência crescente mais longa com soma máxima é .
- No segundo exemplo, a subsequência crescente mais longa com soma máxima é .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB