Snack Party
InterviewTime limit1sMemory limit1024 MB
Given N days each with one positive snack rating, pick a strictly increasing subsequence (starting above 0) to maximize the sum of chosen ratings.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Array, Greedy, Sorting
- Solved
- No attempts yet
Problem
Seoul is a cat with a picky palate. Because Seoul is picky, she eats only snacks tastier than the last snack she ate. Seoul finds a snack tastier the higher its rating is.
Her owner wants to hold a snack party for Seoul over N days. On each day of the party Seoul may eat a snack or may not, but only one snack is given per day. The owner would like to hold the most satisfying snack party possible for Seoul. The most satisfying snack party is the one with the maximum satisfaction, computed as follows.
(satisfaction of the party) = (sum of the ratings of all snacks Seoul eats while the party runs)
The owner is an INFJ and likes making plans, so they want to write a schedule recording the number of party days and the rating of the snack that can be given on each day.
Making the party schedule is something the owner enjoys, so they will gladly do it even while busy, but looking at the finished plan and computing the maximum satisfaction of the snack party in advance is something they have no time for at all. The owner has too much to do: feeding Seoul, playing with Seoul, cleaning Seoul's litter box, and more.
For the busy owner, write a program that reads the schedule and computes the maximum satisfaction of the snack party in advance. The rating of the last snack Seoul ate before the party starts is 0.
Input
The first line gives the integer N (1 ≤ N ≤ 1,000).
Lines 2 through N + 1 give the snack ratings. Line i + 1 (1 ≤ i ≤ N) gives the rating of the snack that can be given on day i of the party, and every rating is a positive integer not exceeding 100,000.
Output
On the first line, print the maximum satisfaction of the snack party schedule given in the input.