Given daily prices of a stock, what’s the maximum possible profit one can generate by first buying one share of that stock on a certain day and then selling that share at least one day later?
Input: [ 2, 3, 10, 6, 4, 8, 1]
Output: 8
For a maximum possible profit of 8 one can buy a share on day 0 at the price of 2 and then sell it on day 2 at the price of 10. Note that one isn’t allowed to first sell (“sell short”) for 10 and then buy (“buy to cover”) later for 1 which could have generated a higher profit.
Input Parameters: The function has one argument, an integer array with daily prices.
Output: Return an integer, the maximum possible total profit from buying and then selling a share. If no profit can be generated, return -1.
● 2
● 1
We provided four solutions.
Calculating maximum possible profit is as simple as finding the maximum difference between two elements such that the larger element appears after the smaller number. We will try the following approach:
Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.
O(n^2) where n denotes the length of the input array.
As we are using two nested loops, it will take O(n^2). Hence complexity will be O(n^2).
O(1).
As we are not storing anything extra other than some integer variables which will take constant space.
O(n) where n denotes the length of the input array.
As auxiliary space used is O(1) and to store input it will take O(n), to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).
In this method, instead of taking the difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) The maximum difference found so far (max_diff).
2) The minimum number visited so far (min_element).
O(n) where n denotes the length of integer array arr.
As we are using a single loop to calculate the maximum difference (maximum profit) and we are maintaining the minimum element found so far and maximum possible difference, it will take O(n). Hence complexity will be O(n).
O(1).
As we are not storing anything extra other than some integer variables which will take constant space.
O(n) where n denotes the length of integer array arr.
As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).
In optimal_solution1, we were maintaining the minimum element found so far to calculate the maximum possible difference, here we will keep track of the maximum element from the right side.
O(n) where n denotes the length of integer array arr.
As we are using a single loop and iterating over it from the reverse side to calculate the maximum difference (maximum profit) and we are maintaining the maximum element found so far and maximum possible difference, it will take O(n). Hence complexity will be O(n).
O(1).
As we are not storing anything extra other than some integer variables which will take constant space.
O(n) where n denotes the length of integer array arr.
As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence total space complexity will be O(1) + O(n) + O(1) = O(n).
We want to calculate the maximum possible profit by buying and selling stock exactly once, in simple words to calculate the maximum difference between two elements such that the larger element appears after the smaller number. We can follow the below-mentioned approach:
First, find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now, this problem turns into finding the maximum sum subarray of this difference array. We can also optimise it further to make it work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and maximum sum in the same loop.
O(n) where n denotes the length of integer array arr.
As we are using a single loop and iterating over it, it will take O(n). Hence complexity will be O(n).
O(1).
As we are not storing anything extra other than some integer variables which will take constant space.
O(n) where n denotes the length of integer array arr.
As auxiliary space used is O(1) and to store input it will take O(n) for storing arr of size n, to store output it will take constant space as output is a single integer. Hence
total space complexity will be O(1) + O(n) + O(1) = O(n).