Maximum Profit from given array of Stock Prices - Programming Problem

$\mathtt{REFERENCE}$ @ Interve Cake

Problem Definition

You are given an array of Stock Prices. Index of the array represents the time corresponding to a price. Smaller index represents past time and larger index represents future time.

Now you need to write a method that takes the array as an input and returns the best profit that could be made by buying 1 stock and selling 1 stock.

Example

  int[] stockPrices = new int[] {15, 5, 10, 25, 55, 1};

  getMaxProfit(stockPrices); // returns 50 (buy at $5 and sell at $55)

    

Only the stock bought at past can be sold in the future. So the time difference must be at least 1 for conducting the transaction.

Brute Force Solution

Brute Force solution would be to consider every valid pair and keep updating the maximum profit that can be made.

  /**
   * Brute Force Approach to calculate the profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;

    for (int i = 0; i < stockPrices.length; i++) {
      for (int j = i+1; j < stockPrices.length; j++) {
        int profit = stockPrices[j] - stockPrices[i];
        if (profit > maxProfit) {
          maxProfit = profit;
        }
      }
    }

    return maxProfit;
  } // getMaxProfit

    

Time Complexity

The outer loop runs for all the prices i.e. $n$ times $n$ being the number of stock prices.

For the first outer loop, the inner loop runs for $n-1$ times
For the second outer loop, the inner loop runs for $n-2$ times
For the third outer loop, the inner loop runs for $n-3$ times and so on until 0.

So, the two loops run for $(n-1) + (n-2) + (n-3) + ...... + 2 + 1 + 0 \approx n^2$ times. Operations inside the loops are constant time operations.

$\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(1)$.

Linear Time Solution

The problem can be solved in linear time by traversing the array only once. For each item traversed, we store the minimum value of the stock seen so far and update the maximum profit greedily.

  /**
   * Linear Time solution to find the max profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;
    int minPrice = stockPrices[0];

    for (int i = 1; i < stockPrices.length; i++) {
      int profit = stockPrices[i] - minPrice;
      if (maxProfit < profit) {
        maxProfit = profit;
      }

      if (minPrice > stockPrices[i]) {
        minPrice = stockPrices[i];
      }

    }
    return maxProfit;
  } // getMaxProfit

    

Time Complexity

In this solution, the stock prices are accessed only once. And for the stock price the processing is constant time.

$\therefore$ The overall time complexity is ${\cal O}(n)$. The Space complexity remains ${\cal O}(1)$.

Implementation

---

---

---