Sell the Items
Sanky has got K (1 <= K <= 1500) items and wants to sell them. He sells one item per day and intends to maximize the profit over a period of time.
Items have some characteristic features:
- Numbering of items are done from 1 to K and kept sequentially in a container which is open at both ends. On any day, Sanky can retrieve one item from either end of his box of items.
- Durability of items improve with time and thereby increasing their price.
- The items are not uniform: some are better and have higher value. Item x has value v(x) (1 <= v(x) <= 500).
- Buyer pay more for items that have higher durability: a buyer will pay v(x)*d for item of durability d.
Given the values v(x) of each of the items kept in order of the index x in the container, what is the maximum value Sanky can receive if he orders the sale of the items optimally?
The first item sold on day 1 has durability d=1. Each subsequent day durability increases by 1.
The first line consists of the number of items, K.
Next K lines contains a single integer per line giving the value of item v(x).
Input is terminated by End Of File.
There will be maximum 25 test cases.
The maximum profit Sanky can receive by selling the items.
Problem Setter: Nitish Agarwal