Solution For Maximum Profit From Trading Stocks

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& 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)

Step by Step Implementation For Maximum Profit From Trading Stocks

class Solution {
    public int maxProfit(int[] prices) {
        // check for empty or null array
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // initialize min price and max profit
        int minPrice = prices[0];
        int maxProfit = 0;
        
        // scan through the prices array
        for (int i = 1; i < prices.length; i++) {
            // update max profit if necessary
            if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
            
            // update min price if necessary
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
        }
        
        return maxProfit;
    }
}

Say you have an array for which the i-th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

def maxProfit(prices):

# Base case
if len(prices) == 0:
    return 0

# Initialize variables
min_price = prices[0]
max_profit = 0

# Loop through prices
for i in range(len(prices)):
    # Update min_price
    if prices[i] < min_price:
        min_price = prices[i]
    # Update max_profit
    if prices[i] - min_price > max_profit:
        max_profit = prices[i] - min_price

return max_profit

var maxProfit = function(prices) {
    let minprice = prices[0]; 
    let maxprofit = 0; 
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minprice)
            minprice = prices[i]; 
        else if (prices[i] - minprice > maxprofit)
            maxprofit = prices[i] - minprice; 
    }
    return maxprofit; 
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int max_profit = 0;
        int min_price = INT_MAX;
        for (int i = 0; i < prices.size(); 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;
    }
};

using System; 

public class Solution {
    public int MaxProfit(int[] prices) {
        int minprice = Int32.MaxValue; 
        int maxprofit = 0; 
        for (int i = 0; i < prices.Length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i]; 
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice; 
        }
        return maxprofit; 
    }
}