Maximum Sum of Increasing Subsequence

Given a sequence of integers, determine the maximum sum of a strictly increasing subsequence. A subsequence is obtained by deleting zero or more elements from the original sequence without changing the order of the remaining elements. Formally, for an array \(a\) of length \(n\), define a dynamic programming state as follows:

\[ \text{dp}[i] = a[i] + \max_{0 \le j a[j]} (\text{dp}[j]) \]

The answer is \(\max_{0 \le i < n} (\text{dp}[i])\). You are required to use an approach based on dynamic programming to solve this problem.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) (where (1 \le n)) representing the number of elements in the sequence. The second line contains (n) space-separated integers.

outputFormat

Output a single integer to standard output (stdout): the maximum sum of any strictly increasing subsequence.## sample

6
10 22 9 33 21 50

115