PROBLEM LINKS:
Difficulty:
Easy
Pre-requirements:
Ad-hoc
Problem:
Prices of a share for N hours are given. A share can be bought at any hour, but it can be sold only after it is bought. The share can be bought and sold at most once. Find the maximum profit that can be made.
Explanation:
A few observations: To make maximum profit share has to be bought at minimum price and to be sold at maximum price possible at the same time buying should always precede selling.
Maintain a prefix minimum array preMin where ith element is the minimum element in the range [0,i] in the price array. It can be computed in O(N).
Iterate through the share prices, and for every price that can be sold, find the minimum price that the share can be bought that precedes the selling using preMin array that gives the corresponding profit. Find the maximum of such profits. This can also be done in O(N).
overall complexity: O(N) for each Test case.
Authors Solution:
can be found here