Maximum Profits
We'll discuss how to write a function that can reap the maximum profits from a day's stock data. We'll discuss both the simple brute-force solution and an elegant solution to this problem.
Instructions
Suppose we could access yesterday’s prices for a certain stock as a chronological list. Write a function that takes the list and returns the highest profit possible from one purchase and one sale of the stock yesterday.
For example, a stock price list of [18, 7, 5, 8, 11, 9] Shows that the stock started at i8 and ended at , going through the numbers chronologically. There is at least a 1-minute difference between the stock prices.
Taking that array as input, our function should return 6, the maximum possible profit from buying when the price was s and selling when the price was ii.
If no profit can be made, return 8.
No “shorting” — you must buy befDre you sell. You may not buy and sell in the same time step.
Input: Array of Numbers
Output: Number
Hints
• We’ll have to convert this array of stock prices into possible profits
• Think about the fact that this is a chronologically ordered list.
function getMaxProfit(prices) {
// Your code here 3
}
Solution
let count = 0; 2
function getMaxProfit(prices) {
const possibleProfits = [];
for(let i = 0; i < prices.length; i++) (
for(let j = i; j < prices.length; j++) {
possibleProfits.push(prices[j] - prices[i]);
count++;
return Math.max(...possibleProfits);
}
getMaxProfit([1, 2, 3]);
console.log(count);
}
The Loop
The second line in the loop updates our minimum price if necessary.
The third line updates the maximum profit if the profit from buying at our current minimum price and selling at the current number is greater than the current max profit.
At the end, we return that maximum profit.
Time
This time, we go through the array only once, giving us an efficiency of:
0(n)
Much better than o(n^2)
Space
We don’t create any arrays or store values across lDop iteratiDns. All we track is the two variables declared at the beginning. We maintain the same amount of information regardless of array size, so we have a space complexity of
0(1)
It’s the best we can get.
Conclusion
This is the solution that would win the interviewer over. It’s difficult and it shows the ability to logically deal with hoth numbers and time. It’s elegant, short and sweet. It has the best time and space complexities imaginable for this type of problem.
Take away the idea that there are times when you can turn an o(n^2) solution into an O(n) solution with some critical thinking. Occasionally, keeping track of important values and updating them in the loop will vastly speed up a function.
Top comments (0)