Max Profits of Stock Prices

Question

I am trying to figure out a divide and conquer algorithm with O(nlogn) time to solve the following real world problem -

Suppose we have an array of stock prices. Come up with an algorithm that prints out an array with the max profit for every day i in the array.

So for example, if we had array A = [4,6,2,1], our days would represent each index, and our output would be an array with values [2,-4,-1,-1] with the last day being value -A[i].

I have figured out a brute force algorithm that -

   1.) Scans the array for max after A[i]
   2.) Subtracts A[i] with max, places value in A', iterates to next day
   3.) When max reaches itself, repeat steps 1 & 2
   4.) When you reach the end, the value is -A[i], return

Also, I am confused if the time complexity of the algorithm described above would be o(n), or o(n^2). The biggest cost in the algorithm is finding the max, everything else is o(1).

Can someone please help me? Thanks

Answer 1

You don't want divide an conquer here. You can do this in linear time (O(n)). Here is the code in java, but you can do this in any language:

int[] maxProfit = new int[prices.length];
int maxPrice = 0;
for (int i = prices.length - 1; i >= 0; i--) {
 maxProfit[i] = maxPrice - prices[i];
 maxPrice = Math.max(maxPrice, prices[i]);
}

This assumes you have an array, prices, which contains your prices as integers.

The key here is that you can get all the information you need by starting from the end and going backward.