Do you know what MSIS is? MSIS is the abbreviation for Maximum Sum Increasing Subsequence. It is a subsequence of a given list of integers, whose sum is maximum and in the subsequence, all elements are sorted in strictly increasing order.
Given an array A of n positive integers. Write a program to find the sum of the elements of the MSIS.
N.B: A sub -sequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
First line of the input will contain an integer n, the number of elements in the array A. The second line will contain n space separated integers, the elements of the array A.1 ≤ n ≤ 1051 ≤ Ai ≤ 109
Print the sum of the elements of the MSIS of the given array A.
3 5 1 3
All increasing subsequences have been listed below:Sequence: , Sum: 5Sequence: , Sum: 1Sequence: , Sum: 3Sequence: [1, 3], Sum: 4Maximum sum is 5. So, the sum of the elements of the MSIS is 5.
5 8 54 17 58 45