The input consists of a sequence of numbers a[1], a[2, ] . . . , a[n]. Your task is to designan O(n2) algorithm that finds an increasing subsequence with the maximum possible sum.An increasing subsequence is given by a sequence of indices 1 ? i1 < i2 < … < ik ? nsuch that a[i1] ? a[i2] ? … ? a[ik]. Note the the indices defining the subsequence are notnecessarily consecutive numbers.

Your algorithm should work in time O(n2).

For example, for sequence 1, 14, 5, 6, 2, 3, the increasing subsequence 1, 14 has the largestsum 1 + 14 = 15. (1,5,6 is another increasing subsequence but its sum, 1 + 5 + 6 = 12 issmaller.)

Input specification: the first line contains n and the second line contains a1,…,an.Numbers on the same line are separated by spaces. You may assume that n is not biggerthan 10, 000 and all the numbers fit in int.

Output specification: the output contains the maximum possible sum of an increasingsubsequence (note: you do not have to compute the subsequence itself, just the maximumpossible sum).

*i have the inputs too