Hello,↵
↵
During my practice, I wanted to solve the problem [Div 2 343, D: Babaei and Birthday Cake](http://codeforces.me/contest/629/problem/D). In summary, we are given a sequence $A = a_1, \ldots, a_n$ of $n$ positive numbers and we should find a strictly increasing subsequence of this sequence with maximum sum. A straightforward dynamic programming solution defines a state $f(i)$ as the maximum sum of an increasing subsequence ending at element $i$. $f(0) = 0$ and $f(i) = \max_{1 \leq j < i} f(j)+a_i$ for $1 \leq i \leq n$. The editorial explains how to implement this dynamic programming solution using segment trees in O(n log n) time.↵
↵
Another solution that is also well known is to use binary search with a little modified dp recurrence. One such recurrence is to define $f(i)$ as the maximum sum of a strictly increasing subsequence whose end is at most $a_i$. One can consider the elements in the order of their appearance. For element $i$, the algorithm finds the largest previous element $v$ such that $a_v < a_i$ (can be done using std::set::lower_bound) and we would have $f(i) = f(v)+a_i$. We then remove all elements $f(k)$ where $a_k > a_i$, $k < i$ and $f(k) \leq f(i)$.↵
↵
I implemented the solution in C++ [here](http://codeforces.me/contest/629/submission/16561046). I tried to implement the solution in Java but I was not able to find a good equivalent of the [std::set::lower_bound](http://www.cplusplus.com/reference/set/set/lower_bound/). The equivalent I know about is the [ceiling method](https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#ceiling%28E%29) in TreeSet class however this method returns the value of the element other than an iterator to it. I wonder whether anybody knows an equivalent to std::set::lower_bound in Java.↵
↵
Sorry for the long post :)↵
↵
During my practice, I wanted to solve the problem [Div 2 343, D: Babaei and Birthday Cake](http://codeforces.me/contest/629/problem/D). In summary, we are given a sequence $A = a_1, \ldots, a_n$ of $n$ positive numbers and we should find a strictly increasing subsequence of this sequence with maximum sum. A straightforward dynamic programming solution defines a state $f(i)$ as the maximum sum of an increasing subsequence ending at element $i$. $f(0) = 0$ and $f(i) = \max_{1 \leq j < i} f(j)+a_i$ for $1 \leq i \leq n$. The editorial explains how to implement this dynamic programming solution using segment trees in O(n log n) time.↵
↵
Another solution that is also well known is to use binary search with a little modified dp recurrence. One such recurrence is to define $f(i)$ as the maximum sum of a strictly increasing subsequence whose end is at most $a_i$. One can consider the elements in the order of their appearance. For element $i$, the algorithm finds the largest previous element $v$ such that $a_v < a_i$ (can be done using std::set::lower_bound) and we would have $f(i) = f(v)+a_i$. We then remove all elements $f(k)$ where $a_k > a_i$, $k < i$ and $f(k) \leq f(i)$.↵
↵
I implemented the solution in C++ [here](http://codeforces.me/contest/629/submission/16561046). I tried to implement the solution in Java but I was not able to find a good equivalent of the [std::set::lower_bound](http://www.cplusplus.com/reference/set/set/lower_bound/). The equivalent I know about is the [ceiling method](https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#ceiling%28E%29) in TreeSet class however this method returns the value of the element other than an iterator to it. I wonder whether anybody knows an equivalent to std::set::lower_bound in Java.↵
↵
Sorry for the long post :)↵
