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
Method 1 - Brute force
Clearly there is an O(n2) 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?
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:
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:
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.
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.
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:
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
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(n2) 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.
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
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.
- 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.
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
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
0 comments:
Post a Comment