Scribble 13: Maximize Profit

This is a really interesting problem. Here’s the problem statement:

Given an array of integers that represents the worth of stock on consecutive days, find the maximum profit that can be earned by buying stock on any day and then selling it on another day in the future.

For example:
The Array: [9,1,5,4,6,2]
Output: 5 (buy when price = 1, sell when price = 6)

Let’s dive into the solution:

Approach 1

The naive solution is to traverse through the array using a double nested loop i, j where j>i for all values of i (i values ranging from 0 to array.length-1) and finding profit that can be earned by buying stock at price array[i] and selling at array[j] and thereby calculating the maximum profit possible.

Time complexity: O(N2) because we use a doubly nested loop

Space complexity: O(1) because we do not use any extra storage space

Approach 2

This time let’s try to do better than O(N²):

Note that to maximise the profit, it is required that the cost price (cp) be the minimum and the selling price (sp) be the maximum value possible such that the said sp happens on a day after the said cp happens.

We can calculate the profit earned by selling stock on day i by calculating (array[i]-minimum cp before day i). This can be calculated for all i ranging from [0->array.length-1] and therefore the maxProfit can be calculated.

To do so:

Set cp = Integer.MAX_VALUE initially.
Loop through the array in a for loop i
At every index i, if array[i]>cp then calculate profit on this day by calculating array[i]-cp and update maxProfit if needed
Else i.e. if selling that day will give profit in -ve i.e. if that day’s price is < min cp that ever happened before it (i.e. basically if array[i]<array[j] where j lies in [0, i-1]), then we reset cp to be = array[i]. This new cp becomes the min. cp happening before all indices that lie after i

Time complexity: O(N) because we loop through the array once

Space complexity: O(1) because we do not use any extra storage

Here’s the code for this solution in Java:

public int maximizeProfit(int[] array) {
      int cp, maxProfit;
      cp = Integer.MAX_VALUE;
      maxProfit = 0;
      for(int i = 0;i<array.length;i++) {
          if(array[i]>cp) {
              maxProfit = Math.max(maxProfit, array[i]-cp);
          }
          else {
              cp = array[i];
          }
      }
      return maxProfit;
}

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂

Share this:

Related