We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This problem is a two-way, least price stock problem.
The canonical stock span problem can be formulated as:
Consider a stock price sampled on the kth day, denoted price[k], What is the largest i, where i < k, such that for all i <= j < k, price[j] <= price[k]? In other words, given a kth day stock price price[k], for how many consecutive previous days has price[k] reigned as the greatest?
For this problem, we need to solve two instances of the stock span problem, one going back in time and one going "forward" in time; furthermore, rather than considering how long price[k] has been the greatest for, we need to consider how long price[k] has been the smallest for. I shall denote them problem 1 and problem 2:
Problem 1. Consider a stock price sampled on the kth day, denoted price[k]. What is the largest i, where i < k, such that for all i <= j < k, price[j] >= price[k]? In other words, given a kth day stock price price[k], for how many previous consecutive days has price[k] been the lowest?
Problem 2. Consider a stock price sampled on the kth day, denoted price[k], What is the largest m, where k < m, such that for all k <= l < m, price[k] <= price[m]? In other words, given a kth day stock price price[k], for how many next consecutive days will price[k] have been the lowest?
Combine the results from problem 1 and 2 to determine the largest window that a given number is a minimum for. Be careful with counting when you combine the results.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Min Max Riddle
You are viewing a single comment's thread. Return to all comments →
This problem is a two-way, least price stock problem.
The canonical stock span problem can be formulated as:
For this problem, we need to solve two instances of the stock span problem, one going back in time and one going "forward" in time; furthermore, rather than considering how long price[k] has been the greatest for, we need to consider how long price[k] has been the smallest for. I shall denote them problem 1 and problem 2:
Combine the results from problem 1 and 2 to determine the largest window that a given number is a minimum for. Be careful with counting when you combine the results.