Max Profit for Stocks

Problem Statement

Given an array for which the $i$ th element is the price of a given stock on day $i$ , maximize the profit you can make. You are only permitted to complete at most one transaction (i.e., buy once and sell once only one share of the stock).

Note that you cannot sell a stock before you buy one. Prices are all non-negative integers.

class Solution {
    public static int maxProfit(int[] prices) {
        // your code here
        
    }
}

Test Cases

Test Case 1

Input: [2,1,5,3,6,4]
Output: 5
Buy on day 1 (price = 1) and sell on day 4 (price = 6), profit = 6-1 = 5.

Test Case 2

Input: [2,1,3]
Output: 2
Buy on day 1 (price = 1) and sell on day 2 (price = 3), profit = 3-1 = 2.

Hints

Click Here

Think about if we were to sell it at day $i$ , do we know what day we should have bought the stock at in order to maximize profit?

Followup

What if multiple trades can happen, how would you modify your solution? What would be the runtime?

Click Below to see the Solution

Click Here

Algorithm

Essentially the problem can be reduced down to a mathematical formulation of finding: max of array[i] - array[j] such that i >=j.
A brute force approach would be to try every single $i$ and $j$ combinations. The runtime is $O(n^2)$ . Can we do better?
Think about if we were to sell it at day $i$ , do we know what day we should have bought the stock at in order to maximize profit?
If we were to sell at day $i$ , we should have bought the stock at the cheapest price on a day $j$ such that $j<=i$ to maximize profit.
From an array point of view, if we were to sell at day $i$ and maximize profit, we should have bought it at the cheapest price that is on the left of index $$i$ of the array. Therefore, if we iterate through the array left to right, we can keep track of the cheapest price to have bought the stock in order to maximize profit if we sell at day$ i$$ by keeping track of cheapest price so far. i.e. find min(prices[0:i])
Then we maximize on all the possible days we can sell it at.

Let’s look at this example: [2,1,5,3,6,4]
If we were to sell on day 0, we buy and sell on the same day, profit is 0, max profit so far is 0.
If we were to sell on day 1, the lowest price we can buy at before day 1 is 1 (on day 1), profit is 0, max profit so far is 0.
If we were to sell on day 2, the lowest price we can buy at before day 2 is 1 (on day 1), profit is 4, max profit so far is 4.
If we were to sell on day 3, the lowest price we can buy at before day 3 is 1 (on day 1), profit is 2, max profit so far is 4.
If we were to sell on day 4, the lowest price we can buy at before day 4 is 1 (on day 1), profit is 5, max profit so far is 5.
If we were to sell on day 5, the lowest price we can buy at before day 5 is 1 (on day 1), profit is 3, max profit so far is 5.
Thus the overall max profit is 5, by buying on day 1 and selling on day 4.

Code


public class Solution {
    public int maxProfit(int[] prices) {
        int minpriceSoFar = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            // update the minpriceSoFar as we loop through the array
            if (prices[i] < minpriceSoFar)
                minpriceSoFar = prices[i];
            // the maximal profit we can achieve by selling on day i is the difference between day i's price and minpriceSoFar
            // update maxprofit if day i's maximal profit is larger than our previous maxprofit
            maxprofit = Math.max(maxprofit, prices[i] - minpriceSoFar);
        }
        return maxprofit;
    }
}

Runtime Analysis

We iterate through the array once, and it takes constant work per iteration so the computational complexity is $O(n)$ . Auxiliary Space complexity is $O(1)$ since two variables are used which is a constant number.

Followup

If we are allowed to do multiple transactions, we can get our maximal profit by adding up all the increases from day $j$ to day $i$ for all $j <= i$ through one single pass.
The time and space complexity are still $O(n)$ and $O(1)$ .