How to find the maximum amount between elements of an increasing subsequence?

The general idea is exactly the same as for the ordinary task where you need to maximize the length of the sequence. It is solved using a segment tree or Fenwick tree. References to the ideas http://e-maxx.ru/algo/fenwick_tree http://e-maxx.ru/algo/segment_tree .

We need to be able to quickly find (with log n) a key less than the given one with a maximum value. (Equivalent to finding the maximum in the segment).

pseudocode

for (int i=0;i<N;i++) Tree.update(A[i], Tree.search(A[i]) + A[i] ) 

The answer is maximum over all A [i]. There if that analysis is on this link.

Below is more expanded.

and what exactly is not clear?) If you figured out how to write a tree, then it remains only to write this cycle. Why this is so: if we continue the sequence, then it is true that the previous element was no more than the current one and of all such it is necessary to continue the most profitable (by the amount already accumulated). Why 2 statement is true - by contradiction, let it become advantageous to continue a1 <= a2 <= a3 ... <= C <= ... (C - current) and there is b1 <= b2 <= b3 <= ... <= C such that a1 + a2 + a3 + ... <b1 + b2 + b3 + ... (strict negation of 2 points), then we can replace the entire initial chain ai with bi, which will improve the answer -> get a contradiction. Hence the greedy algorithm is correct.

Algorithm: we take the current element C, we look at all the sequences q1 <= q2 <= qn <= C, from all these we choose it with the maximum sum q1 + q2 + ... + qn and try to continue it (if there are none, then we start a new sequence) .

Note that the sequence itself does not interest us, we only need to know its last element and the sum of its members.

Let's build a tree, a key is the last element, a value is a sum.

Now just go through the array from left to right, find the maximum on the segment (-inf, C] (if there is nothing, then set the answer to maximum 0). Change the value of the current element to the maximum found + C.

The answer is the maximum of all A [i] from the array. The complexity of the O (n log N) time, O (n) or O (n log n) memory (depending on the type of tree).

I do not write the code specifically.

For each element, you need to keep the maximum amount that ends strictly in it.

It is necessary somehow for the current element to calculate the answer for the logarithm.

I will assume that the placement of the minimum last number for the given response in the map . Although I can not justify that the asymptotics will be acceptable, because I have to go through the elements of the map in the loop until the answer is found.