The input consists of a sequence of numbers a[1], a[2, ] . . . , a[n]. Your task is to design an 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 ≤ n such that a[i1] ≤ a[i2] ≤ … ≤ a[ik]. Note the the indices defining the subsequence are not necessarily 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 largest sum 1 + 14 = 15. (1,5,6 is another increasing subsequence but its sum, 1 + 5 + 6 = 12 is smaller.)
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 bigger than 10, 000 and all the numbers fit in int.
Output specification: the output contains the maximum possible sum of an increasing subsequence (note: you do not have to compute the subsequence itself, just the maximum possible sum).
Sample Solution
