Problem
Suppose we are given an array of n integers representing stock prices
on a single day. We want to find a pair (buyDay, sellDay), with buyDay
≤ sellDay, such that if we bought the stock on buyDay and sold it on
sellDay, we would maximize our profit.
OR
Given an array arr[] of integers, find out the difference between any two elements
such that larger element appears after the smaller number in arr[].
Example
Input = {5 10 4 6 7}
Output = 5,10 => buy at 5 and sell at 7
Solution
Method 1 - Brute force
Clearly there is an O(n
2) solution to the algorithm by
trying out all possible (buyDay, sellDay) pairs and taking the best out
of all of them. However, is there a better algorithm, perhaps one that
runs in O(n) time?
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int i, j;
for(i = 0; i < arr_size; i++)
{
for(j = i+1; j < arr_size; j++)
{
if(arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
Method 2 - Divide and Conquer
If we have a single day, the best option is to buy on that day and
then sell it back on the same day for no profit. Otherwise, split the
array into two halves. If we think about what the optimal answer might
be, it must be in one of three places:
- The correct buy/sell pair occurs completely within the first half.
- The correct buy/sell pair occurs completely within the second half.
- The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.
We can get the values for (1) and (2) by recursively invoking our
algorithm on the first and second halves. For option (3), the way to
make the highest profit would be to buy at the lowest point in the first
half and sell in the greatest point in the second half. We can find
the minimum and maximum values in the two halves by just doing a simple
linear scan over the input and finding the two values. This then gives
us an algorithm with the following recurrence:
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
Using the
Master Theorem
to solve the recurrence, we find that this runs in O(n lg n) time and
will use O(lg n) space for the recursive calls. We've just beaten the
naive O(n
2) solution!
Method 3 - Optimized divide and conquer
But wait! We can do much better than this. Notice that the only
reason we have an O(n) term in our recurrence is that we had to scan the
entire input trying to find the minimum and maximum values in each
half. Since we're already recursively exploring each half, perhaps we
can do better by having the recursion also hand back the minimum and
maximum values stored in each half! In other words, our recursion hands
back three things:
- The buy and sell times to maximize profit.
- The minimum value overall in the range.
- The maximum value overall in the range.
These last two values can be computed recursively using a
straightforward recursion that we can run at the same time as the
recursion to compute (1):
- The max and min values of a single-element range are just that element.
- The max and min values of a multiple element range can be found by
splitting the input in half, finding the max and min values of each
half, then taking their respective max and min.
If we use this approach, our recurrence relation is now
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!
Method 4 - Use the difference between adjacent element
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 problems turns into finding the maximum sum subarray of this
difference array.
int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1. The array will hold
// the difference of adjacent elements
int diff[n-1];
for (int i=0; i < n-1; i++)
diff[i] = arr[i+1] - arr[i];
// Now find the maximum sum subarray in diff array
int max_diff = diff[0];
for (int i=1; i<n-1; i++)
{
if (diff[i-1] > 0)
diff[i] += diff[i-1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
Example
input =
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 5 - Optimizing the diff approach
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.
int maxDiff (int arr[], int n)
{
// Initialize diff, current sum and max sum
int diff = arr[1]-arr[0];
int curr_sum = diff;
int max_sum = curr_sum;
for(int i=1; i<n-1; i++)
{
// Calculate current diff
diff = arr[i+1]-arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
Time Complexity: O(n),
Auxiliary Space: O(1)
Method 6 - Dynamic programming (Preferred and easy :))
But wait a minute - we can do even better than this! Let's think
about solving this problem using dynamic programming. The idea will be
to think about the problem as follows. Suppose that we knew the answer
to the problem after looking at the first k elements. Could we use our
knowledge of the (k+1)st element, combined with our initial solution, to
solve the problem for the first (k+1) elements? If so, we could get a
great algorithm going by solving the problem for the first element, then
the first two, then the first three, etc. until we'd computed it for
the first n elements.
Let's think about how to do this. If we have just one element, we
already know that it has to be the best buy/sell pair. Now suppose we
know the best answer for the first k elements and look at the (k+1)st
element. Then the only way that this value can create a solution better
than what we had for the first k elements is if the difference between
the smallest of the first k elements and that new element is bigger than
the biggest difference we've computed so far. So suppose that as we're
going across the elements, we keep track of two values - the minimum
value we've seen so far, and the maximum profit we could make with just
the first k elements. Initially, the minimum value we've seen so far is
the first element, and the maximum profit is zero. When we see a new
element, we first update our optimal profit by computing how much we'd
make by buying at the lowest price seen so far and selling at the
current price. If this is better than the optimal value we've computed
so far, then we update the optimal solution to be this new profit.
Next, we update the minimum element seen so far to be the minimum of the
current smallest element and the new element.
Since at each step we do only O(1) work and we're visiting each of
the n elements exactly once, this takes O(n) time to complete!
Moreover, it only uses O(1) auxiliary storage. This is as good as we've
gotten so far!
As an example, on your inputs, here's how this algorithm might run.
The numbers in-between each of the values of the array correspond to the
values held by the algorithm at that point. You wouldn't actually
store all of these (it would take O(n) memory!),
Time - O(n), Space - O(1) solution:
public static int findMaxProfit(int[] stockPriceSamples) {
int maxProfit = 0;
int minTillNow = stockPriceSamples[0];
for (int i = 0; i < stockPriceSamples.length; i++) {
int profit = stockPriceSamples[i] - minTillNow;
maxProfit = Math.max(profit, maxProfit);
minTillNow = Math.min(stockPriceSamples[i], minTillNow);
}
return maxProfit;
}
Example
input = {5 10 4 6 7}
i = 0, maxProfit = 0, minTillNow=5
i = 1, maxProfit=5, minTillNow=5
i= 2, maxProfit = 5,minTillNow=4
i=3,maxProfit=5,minTillNow=4
i= 4,maxProfit=5,minTillNow=5
References
