As a bonus challenge, Dip wants not just the maximum-SUM increasing subsequence, but a way to actually reconstruct and display one such winning subsequence on stage. Read N integers. Find the maximum possible SUM (not length) of a strictly increasing subsequence, and also print one valid subsequence achieving it.
Input
Line1: N. Line2: N integers.
Output
Line1: maximum sum. Line2: one valid subsequence achieving it, space-separated.
Constraints
1 ≤ N ≤ 10^4
Sample Input
5 1 101 2 3 100
Sample Output
106 1 2 3 100
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.