In this approach, we traverse the prices array while keeping track of the minimum price seen so far and calculate the maximum profit we could achieve if we sold on that day. The maximum profit is updated accordingly through each iteration.
This approach makes a single pass through the array (O(n) time complexity) and uses constant space (O(1) space complexity).
Time Complexity: O(n), where n is the number of days.
Space Complexity: O(1).
1#include <iostream>
2#include <vector>
3
4int maxProfit(std::vector<int>& prices) {
5 if (prices.empty()) return 0;
6 int min_price = prices[0];
7 int max_profit = 0;
8 for (int i = 1; i < prices.size(); i++) {
9 min_price = std::min(min_price, prices[i]);
10 max_profit = std::max(max_profit, prices[i] - min_price);
11 }
12 return max_profit;
13}
14
15int main() {
16 std::vector<int> prices = {7, 1, 5, 3, 6, 4};
17 std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
18 return 0;
19}This C++ solution uses a similar logic, utilizing STL functions like std::min and std::max to update the minimum price and maximum profit respectively while iterating through the array.
This approach considers all possible pairs of buy and sell days, calculating the profit for each combination. It is straightforward but inefficient due to its O(n^2) time complexity, which is impractical for large inputs.
Time Complexity: O(n^2), where n is the number of days.
Space Complexity: O(1).
1function maxProfit(prices) {
2 let maxProfit = 0;
3 for (let i = 0; i < prices.length; i++) {
4 for (let j = i + 1; j < prices.length; j++) {
5 let profit = prices[j] - prices[i];
6 if (profit > maxProfit) {
7 maxProfit = profit;
8 }
9 }
10 }
11 return maxProfit;
12}
13
14const prices = [7, 1, 5, 3, 6, 4];
15console.log("Max Profit (Brute Force):", maxProfit(prices));This JavaScript solution uses nested for loops to check all sell points after each buy point, calculating and retaining the highest profit estimate formed by these combinations.