Maximum Sum Increasing Subsequence

Given an integer n and an array of n integers, your task is to find the maximum sum of any subsequence in which the elements appear in strictly increasing order. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

If the array is empty (n = 0), the answer is defined to be 0. Otherwise, if no increasing subsequence exists (for example, when all elements are non-increasing), the result should be the maximum individual element. The solution can be implemented using dynamic programming with the recurrence relation:

\( dp[i] = arr[i] + \max_{0 \leq j < i,\, arr[j] < arr[i]}\{dp[j]\} \) with \( dp[i] = arr[i] \) if no such \( j \) exists. The final answer is \( \max_{0 \le i < n} (dp[i]) \).

This problem challenges your ability to manipulate subsequences and use dynamic programming optimally. Strict input/output requirements must be followed, with input read from standard input and output written to standard output.

inputFormat

The input consists of two lines:

1. The first line contains a single integer n (0 ≤ n ≤ 10⁵), which is the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

If n is 0, the second line will be empty.

outputFormat

Output a single integer — the maximum sum of a subsequence in which the elements are in strictly increasing order.

6
1 101 2 3 100 4

106