Best Time to Buy and Sell Stock easy

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i^th 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 is 0.

Steps

1. Initialization: We need to keep track of the minimum price encountered so far (min_price) and the maximum profit (max_profit). Initialize min_price to the first price in the array and max_profit to 0.

2. Iteration: Iterate through the prices array starting from the second element.

3. Comparison: For each price, compare it with the current min_price.

   • If the current price is less than min_price, update min_price to the current price. This means we found a potentially better day to buy the stock.
   • If the current price is greater than min_price, calculate the potential profit (current_price - min_price). Compare this potential profit with max_profit. If the potential profit is greater, update max_profit.

4. Return: After iterating through the entire array, return max_profit.

Explanation

The algorithm uses a single pass through the array to efficiently find the maximum profit. It keeps track of the lowest buying price seen so far. For every subsequent price, it checks if selling at that price would yield a higher profit than the current maximum profit. This avoids the need for nested loops which would result in a less efficient O(n^2) solution.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) return 0; // No profit possible with less than 2 prices

    int min_price = prices[0];
    int max_profit = 0;

    for (int i = 1; i < prices.size(); i++) {
        min_price = min(min_price, prices[i]);
        max_profit = max(max_profit, prices[i] - min_price);
    }

    return max_profit;
}

int main() {
    vector<int> prices1 = {7,1,5,3,6,4};
    cout << "Max Profit (Example 1): " << maxProfit(prices1) << endl; // Output: 5

    vector<int> prices2 = {7,6,4,3,1};
    cout << "Max Profit (Example 2): " << maxProfit(prices2) << endl; // Output: 0

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the number of prices. We iterate through the array once.
• Space Complexity: O(1). We only use a few constant extra variables.