Maximum Profit From Trading Stocks - Leetcode Solution

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.

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.

Example 2:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

Approach: We will loop through the array, maintaining the minimum price seen so far and the maximum profit we can get by selling on a given day (after buying on the earlier days). For each day, we check if the price of the current day is lower than the minimum price seen so far, update the minimum price, and continue to the next day. Otherwise, we calculate the profit we can get by selling on that day (current price - minimum price) and check if it is higher than the maximum profit seen so far. If it is, we update the maximum profit. At the end of the loop, we return the maximum profit.

Algorithm:

1. Initialize minimum price to the first price in the array
2. Initialize maximum profit to 0
3. Loop through the array starting from the second price
4. Calculate the profit we can get by selling on the current day (current price - minimum price)
5. If the profit is higher than the maximum profit seen so far, update the maximum profit
6. If the current price is lower than the minimum price seen so far, update the minimum price
7. At the end of the loop, return the maximum profit

Code:

int maxProfit(vector<int>& prices) { int min_price = INT_MAX; int max_profit = 0; int n = prices.size(); for(int i = 0; i < n; i++){ if(prices[i] < min_price){ min_price = prices[i]; } else if(prices[i] - min_price > max_profit){ max_profit = prices[i] - min_price; } } return max_profit; }

Time Complexity: O(n) where n is the size of the input array (we loop through the array once) Space Complexity: O(1) (we use constant space throughout the entire function)

1