Maior somatorio de subsequência crescente

Você receberá um array de números inteiros. Sua tarefa é encontrar a subsequência estritamente crescente com a maior soma possível.

Definição: Uma subsequência é uma sequência formada a partir de um array original removendo zero ou mais elementos, sem alterar a ordem relativa dos elementos restantes. Por exemplo, no array [5, 1, 4, 2]:

• [5, 4, 2] é uma subsequência (removemos o 1).
• [1, 2] também é uma subsequência.
• [4, 5] não é uma subsequência, pois inverte a ordem original dos elementos.

Exemplo: Dado o array

$$ [1, 101, 2, 3, 20, 4, 5] $$

A subsequência estritamente crescente com a maior soma é:

$$ [1, 101] $$

Na primeira linha será dado um inteiro $n$ representando o tamanho do array. $(1 \le n \le 10^5)$

Na segunda linha será fornecido $n$ inteiros representando o array $a_i$. $(1 \le a_i \le 10^9)$

De como saida o maior somatório de subsequência do array.