Maximum Sum Increasing Subsequence
MediumPractice library · +20 XPrecursiondynamic programmingbinary indexed tree
Given a sequence of N integers A_1, A_2, ..., A_N. Find a subsequence A_{i_1}, A_{i_2}, ..., A_{i_k} such that 1 <= i_1 < i_2 < ... < i_k <= N and A_{i_1} < A_{i_2} < ... < A_{i_k}, and the sum A_{i_1} + A_{i_2} + ... + A_{i_k} is maximized. Print this maximum possible sum.
Input
The first line contains an integer N. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer, the maximum sum of an increasing subsequence.
Constraints
1 <= N <= 200000 -10^9 <= A_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
5 1 101 2 3 100
Output
106
The increasing subsequence with maximum sum is 1, 2, 3, 100, with a sum of 106.
Example 2
Input
3 10 9 8
Output
10
The increasing subsequence with maximum sum is 10 (or 9, or 8), with a sum of 10.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 101 2 3 100
Example 2 input
3 10 9 8