Find the maximum possible profit

Problem Statement

Given an array of stock prices per share for a given share over a time period. Calculate the maximum possible profit per share one could have made . Here we do not consider short selling as an option. The trader must have purchased the stocks before selling it.

The problem statement is a real world definition of the problem called maximum positive difference.

Maximum Positive Difference

For the above two arrays, here are the maximum profit per share one could have made:

  • A : 18.0 (difference between 21 and 3)
  • B : 13.0 (difference between 19 and 6)

What is Maximum Positive Difference?

For a list/array of given numbers A[1..N], the difference between two numbers A[n] – A[m] where n > m is said to be positive difference if A[n] – A[m] > 0

Now, maximum positive difference is the maximum of all such possible positive difference in the list or array.

If we can find the maximum positive difference that would be the maximum profit one could have made in the above problem statement.

Approach to solve the problem

We can solve it in multiple ways, here I define few of them:

Brute Force

This is the first method which comes to my mind and perhaps the easiest one. Just calculate all the difference in increasing order of indices and then find the max difference.

Steps:

  • Initialize the maxDifference with -1
  • Start a loop which runs through the array i = 1 .. N-1
  • Start an inner loop which runs through the array j = i+1 .. N
  • If the difference between A[i] and A[j] is positive, compare with max difference and assign the max value to the maxDifference
  • When the loop breaks, the value in the variable maxDifference will contain the maximum positive difference.

Source Code:

Analysis:

  • We are running two nested loops for the length of the array – quadratic running time.
  • In the body of the loop we are doing few comparisons and assignments – constant running time

Hence, the running time would be quadratic. O(N2)

Space required is constant as we are just using few variables.

An efficient solution

The quadratic running time is an overkill here. Let us try something better. Careful analysis of the problem suggests that, if we can just keep track of few things like the minimum price in the list and the maximum difference in the list, we will be able to find the maximum profit.

Here are the steps:

  • Initialize min with the first element in the array
  • Initialize maxDifference with the difference off second – first element.
  • Start a loop from the second element in the array till the end
  • If the difference of the current element and mid is greater than maxDifference then assign the new difference to the maxDifference
  • If the current element is smaller than the min then assign the current element to min.

Source Code:

Analysis:

  • One loop runs from beginning till end of the array – Linear running time
  • Inside the loop only constant amount of work is performed – Constant running time

Hence, the algorithms running time is O(N)

The space complexity is O(1) as we require few variables which do not depend on the size of the input.

Conclusion

The maximum positive difference question is asked in a lot of interviews, with different words and real world problem frames, just remember the concept.

The second approach can also work if you store the max instead of min while travelling from the end of the array.

For more questions and tricks, stay connected and stay subscribed