La plus longue sous-séquence croissante avec la somme maximale
Étant donné un tableau de
n entiers, vous devez trouver la plus longue sous-séquence croissante de ce tableau. S’il existe plusieurs sous-séquences de longueur maximale, vous pouvez en renvoyer n’importe laquelle.Une sous-séquence d’un tableau se construit en supprimant certains éléments (possiblement aucun) sans modifier l’ordre des éléments restants. Par exemple, si le tableau est , alors est une sous-séquence de , tandis que n’en est pas une, car l’ordre des éléments n’est pas respecté.
💡
Une sous-séquence croissante d’un tableau est une sous-séquence dans laquelle les éléments apparaissent dans un ordre strictement croissant. Par exemple, si le tableau est , alors est une sous-séquence croissante de , alors que ne l’est pas, car les éléments ne sont pas en ordre croissant.
Entrée
La première ligne de l’entrée contient un unique entier
n (1 ≤ n ≤ 1000), correspondant à la longueur du tableau.La deuxième ligne contient
n entiers séparés par des espaces (), qui représentent les éléments du tableau.Sortie
Le programme doit afficher la somme de la plus longue sous-séquence croissante ayant la somme la plus élevée.
Entrée | Sortie |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Explication
- Dans le premier exemple, la plus longue sous-séquence croissante avec la somme maximale est .
- Dans le deuxième exemple, la plus longue sous-séquence croissante avec la somme maximale est .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB