Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 ≤ 105****1 ≤ Ai ≤ 109**

Print the sum of the elements of the **MSIS** of the given array **A**.

Input | Output |
---|---|

3 5 1 3 | 5 |

All increasing subsequences have been listed below: Maximum sum is 5. So, the sum of the elements of the MSIS is 5. |

Input | Output |
---|---|

5 8 54 17 58 45 | 120 |

60% Solution Ratio

tmwilliamlin168Earliest,

user.316334Fastest, 0.0s

fardinabirLightest, 1.7 MB

omar24Shortest, 571B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.