Bitcoin Bubble
InterviewTime limit2sMemory limit2048 MB
Given price segments of consecutive days, find the maximum of the longest window around a day x where no price drops below the price on x, times that price.
- Level
Medium5 of 10
- Topics
- Stack, Prefix sum, Array
- Solved
- No attempts yet
Problem
These days, all eyes and money are on crypto. The stakes are high, and a team of experts who call themselves the FPC (Fabulous People of Crypto) is on the verge of a big move. They call their move "The Bubble".
The Bubble works as follows. One day, the FPC will release a set of classified information that will shake the market to its roots. That day, call it , is the epicenter of their move. To measure the impact of The Bubble, consider the longest sequence of consecutive days, starting on day and ending on day (), for which Bitcoin's price is never lower than its price on day . The impact is the length of this sequence in days multiplied by the price of Bitcoin on day . The starting day and the ending day must lie within the period for which the FPC know the price.
The FPC can predict prices but cannot program. Help them find the biggest possible impact of The Bubble, given that they release the information on an optimal day.
Input
The first line contains a single integer (), the number of price predictions for Bitcoin.
Each of the next lines contains two integers and ( and ). The price is and it lasts for days. The price information is given in chronological order.
Output
Output a single number, the biggest impact The Bubble can have.