Max Priority Queue Implementation with Heap Data structure
Max Priority Queue is a data structure which manage a list of keys(values). And…
August 27, 2020
Say you have an array prices for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Examples
Input: [7,1,5,3,6,4]
Output: 7
Explanation:
- buy on day-2, sell on day-3. Profit (5-1) = 4
- buy on day-4, sell on day-5. Profit (6-3) = 3
Lets try a brute force algorithm. Since we know the constraint that we need to buy the stock before selling it.
private int maxProfit_simpleRecursive(int[] prices, int startIndex) {
if (startIndex >= prices.length) {
return 0;
}
int maxProfit = 0;
for (int i=startIndex; i<prices.length; i++) {
int max = 0;
for (int j=i+1; j<prices.length; j++) {
//when can we sell
if (prices[j] > prices[i]) {
int profit = (prices[j] - prices[i]) + this.maxProfit_simpleRecursive(prices, j+1);
if (max < profit) {
max = profit;
}
}
}
if (maxProfit < max) {
maxProfit = max;
}
}
return maxProfit;
}
public int maxProfit_simple(int[] prices) {
return this.maxProfit_simpleRecursive(prices, 0);
}
Complexity
Above code runs in O(n^n)
.
If we try to draw the input in some sort of graph or line chart. We can see some pattern.
If you look closely, we can keep track of low points, and following high point. And take a sum of such points. We can get the maximum profit.
In the above image, we can take following calculation:
Low-point=1, High-point=5, Profit=4
Low-point=3, High-point=6, Profit=3
Total Profit = 7
public int maxProfit_better(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
int i=0;
int lowPrice = prices[i];
int highPrice = prices[i];
i++;
while (i < prices.length) {
//find low value
while (i < prices.length && prices[i-1] >= prices[i]) {
i++;
}
lowPrice = prices[i-1];
//find high value
while (i<prices.length && prices[i] >= prices[i-1]) {
i++;
}
highPrice = prices[i-1];
max += (highPrice - lowPrice);
}
return max;
}
The code runs in O(n)
time as we are running loop n times only.
Above solution worked and is way faster than our first solution. Lets think more about the second solution. We are just finding low peak and high peak, finding difference and take it.
Instead, can we just take the difference if two consecutive prices are in increasing order. Yes, definitely.
Lets look at the code:
public int maxProfit_better2(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int max = 0;
for (int i=1; i<prices.length; i++) {
if (prices[i] > prices[i-1]) {
max += (prices[i] - prices[i-1]);
}
}
return max;
}
Its again O(n)
Max Priority Queue is a data structure which manage a list of keys(values). And…
Big-O notation In simpler terms, its kind of a unit to measure how efficient an…
Problem Statement You are given an array of integers. And, you have find the…
Problem Statement Given a string s, return the maximum number of unique…
Problem Statement Given an array of integers, find if the array contains any…
Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…