121. Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. (link)

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Solution

Brute Force approach

We examine every potential scenario, purchasing on the ith day and comparing it with all subsequent days for j>i. The maximum profit accrued thus far is stored in a variable, which is then returned.

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;

        for(int i = 0; i< prices.length; i++){
            for(int j=i+1; j<prices.length; j++){
                if(prices[j]>prices[i]){
                    ans = Math.max(ans, prices[j]-prices[i]);
                }
            }
        }
        return ans;
    }
}

Optimal Approach

Suppose we are at the ith index. To maximize profit from selling the stock on the ith day, we aim to purchase it at the lowest price encountered thus far [0, ..., i-1]. Employing this approach, we determine the overall maximum profit across all days and retain the global maximum profit.

To ascertain the profit, it is crucial to maintain the minimum value observed so far.

class Solution {
    public int maxProfit(int[] prices) {
        int least = prices[0];
        int ans = 0;

        for(int price: prices){
            ans = Math.max(ans, price-least);
            if(price<least) least = price;
        }
        return ans;
    }
}