P4 - HEIGHT

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 32M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mr.Hsiung dresses fashionably everyday. Not surprisingly, he only does this because he is overly conscious about his height. He has a sequence of N integers, each representing his height at a certain time. However, he organized them poorly. Mr.Hsiung doesn't care about having all of the heights, so he will take some of them, while keeping their relative order. Additionally, this new subsequence of numbers he has must be strictly increasing, as it wouldn't make sense for him to grow shorter. He also wants the sequence with the sum of its elements being maximal. Help Mr.Hsiung find this sum.

Input Specification

The first line contains the integer N (1 \leq N \leq 1000), the number of elements in the original sequence. The N lines will contain N elements, a positive integer at most 1000. For 50% of test cases, 1 \leq N \leq 10.

Output Specification

Output the maximum sum of Mr.Hsiung's new sequence.

Sample Input 1

5
4
1
2
5
6

Sample Output 1

15

Explanation 1

In this case, the subsequence 4, 5, 6 is optimal.

Sample Input 2

5
10
9
8
7
6

Sample Output 2

10

Explanation 2

In this case, no subsequence containing more than 1 element is increasing. Thus, choosing 10 is optimal.


Comments


  • 1
    alexzhang  commented on Oct. 8, 2018, 9:53 p.m.

    Its possible for a person to stay the same height too....


  • 0
    TypicalToxic  commented on Nov. 22, 2016, 8:04 p.m. edited

    pretty sure sample input 1 contains trailing spaces- had to trim input. EDIT: nvm i think someone fixed it