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.
Examples:
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.
Example 2:
Input:prices = [7,6,4,3,1]
Output:0
Explanation:
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
Approach: Brute Force
- Initialize
maxProfit = 0. - Use two nested loops.
- Outer loop picks a day
ito buy the stock. - Inner loop picks a day
j > ito sell the stock. - For every pair
(i, j), calculate the profit:prices[j] - prices[i]. - If this profit is greater than
maxProfit, updatemaxProfit.
Time Complexity:
Time Complexity = O(n2) Two nested loops. For every element i, check all j > i. Total comparisons = n(n-1)/2 → O(n²)
Space Complexity:
Space Complexity = O(1) No extra data structures used. Only uses a variable maxProfit.
Dry Run
Input: prices = [7, 1, 5, 3, 6, 4]
i = 0, prices[i] = 7 j = 1 → 1 - 7 = -6 → maxProfit = 0 j = 2 → 5 - 7 = -2 → maxProfit = 0 j = 3 → 3 - 7 = -4 → maxProfit = 0 j = 4 → 6 - 7 = -1 → maxProfit = 0 j = 5 → 4 - 7 = -3 → maxProfit = 0 i = 1, prices[i] = 1 j = 2 → 5 - 1 = 4 → maxProfit = 4 j = 3 → 3 - 1 = 2 → maxProfit = 4 j = 4 → 6 - 1 = 5 → maxProfit = 5 j = 5 → 4 - 1 = 3 → maxProfit = 5 i = 2, prices[i] = 5 j = 3 → 3 - 5 = -2 → maxProfit = 5 j = 4 → 6 - 5 = 1 → maxProfit = 5 j = 5 → 4 - 5 = -1 → maxProfit = 5 ... and so on. Final maxProfit = 5 (buy at 1, sell at 6)
Output: 5
Visualisation:
var maxProfit = function(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
if ((prices[j] - prices[i]) > maxProfit) {
maxProfit = prices[j] - prices[i];
}
}
}
return maxProfit;
};
class Solution(object):
def maxProfit(self, prices):
maxProfit = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
profit = prices[j] - prices[i]
if profit > maxProfit:
maxProfit = profit
return maxProfit
public class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}
class Solution {
public:
int maxProfit(vector& prices) {
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
};
int maxProfit(int* prices, int pricesSize) {
int maxProfit = 0;
for (int i = 0; i < pricesSize; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
public class Solution {
public int MaxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.Length; i++) {
for (int j = i + 1; j < prices.Length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
} 
