Our subscribers work at

Solution

You've probably heard of the expression "buy low, sell high" and that's exactly how we're trying to solve our problem today. Our goal is to find the optimal point to buy (lowest point) and optimal point to sell (highest point after we've bought). By finding these two points we can then calculate our profit as follows price we sold at - price we bought at. Let's first focus on finding the low price. This is as easy as using a for loop and updating a min variable any time the current price is lower than our min.

int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    // update our min if the current price is smaller than our current min.
    min = Math.min(min, prices[i]);
}

Now that we understand the logic that we can use to find the low price and therefore the price at which we should buy our stock, now we just need to understand when to sell our stock. This can be accomplished by simply checking if our current stock price is greater than our min, if it is let's simulate selling at that point.

int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    if (prices[i] > min) {
        profit = prices[i] - min;
    }
}

Great now we're recording our profit! However, because we are always reassigning our profit to the current calculation if the current price is greater than our min, we are not guaranteeing that we always store the largest profit. Now, using our two methods of finding the low price and simulating making transactions, with some slight tweaking, we can guarantee that we always store the max profit!

public int largestProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < prices.length; i++) {
        if (prices[i] > min) {
            profit = Math.max(profit, prices[i] - min);
        } else {
            min = prices[i];
        }
    }

    return profit;
}

This problem seems complicated, but really just boils down to the code above. Our solution correctly updates a minimum value as necessary while simultaneously simulating making trades for any prices that is greater than our minimum at the time. Now with our changes we are guaranteeing that we only reassign our profit if it yields a larger value!

# Big-O Analysis
Runtime: O(N) where N is the number of prices.
Space complexity: O(1) as we only need a few variables (regardless of the size of the prices array)