Maximum Sum of Increasing Subsequence

Given an array of integers, your task is to find the maximum sum of any increasing subsequence. An increasing subsequence is defined as a sequence in which each element is strictly greater than its previous element. The dynamic programming formulation for this problem is given by: \(dp[i] = \max\Big( arr[i],\; \max_{0 \le j < i \; \&\&\; arr[j] < arr[i]} (dp[j] + arr[i]) \Big)\). The final answer is \(\max_{i} dp[i]\).

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

Output a single integer which is the maximum sum of an increasing subsequence of the array.

7
4 6 1 3 8 4 6

18