Author: Dhruv Singh
Difficulty
Easy
Problem
Given the total amount of money M at the start and the buying and selling prices for N days, find a buy-day sell-day pair which maximizes M by the end of day N.
Explanation
We are given an integer M, which is the initial amount of money. Also we are given N integers signifying the buying or selling price (both equal) Pi for one car on the ith day (1<=i<=N).
Our task is to maximize M by the end of day N by using atmost one transaction of buying and selling. This means that we can choose to buy a certain number of cars on a day and sell all of them on another day or we can choose not to buy-sell at all. In other words there can be atmost one buy-day sell-day pair. On the buy-day we buy certain of cars at the given buying price of the day using the money M. Thus on any day i we can buy at most X=M/Pi cars. After buying X cars the money left with us will be Y=M%Pi. Now suppose we sell these X cars on day j, then the total money after selling them will be Z=X*Pj + Y.
Here N=2000 is very small, hence we can iterate over all possible buy-day sell-day pairs in O(n2) to find the maximizing pair or we can come to the conclusion that no buy-day sell-day pair will maximize M more than initial value.
Time Complexity
O(n2) to iterate over all possible pairs.
C++ code: V0Y2uU - Online C++ Compiler & Debugging Tool - Ideone.com