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).
1using System;
2
3public class Solution {
4 public int MaxProfit(int[] prices) {
5 if (prices.Length == 0) return 0;
6 int minPrice = int.MaxValue;
7 int maxProfit = 0;
8 foreach (int price in prices) {
9 if (price < minPrice) {
10 minPrice = price;
11 } else if (price - minPrice > maxProfit) {
12 maxProfit = price - minPrice;
13 }
14 }
15 return maxProfit;
16 }
17 public static void Main(string[] args) {
18 Solution sol = new Solution();
19 int[] prices = {7, 1, 5, 3, 6, 4};
20 Console.WriteLine("Max Profit: " + sol.MaxProfit(prices));
21 }
22}This solution in C# performs the same logic as the other implementations, utilizing the maximum integer value as an initial minPrice for comparison against incoming prices, updating as necessary.
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).
1#include <iostream>
2#include <vector>
3
4int maxProfit(std::vector<int>& prices) {
5 int max_profit = 0;
6 for (int i = 0; i < prices.size(); i++) {
7 for (int j = i + 1; j < prices.size(); j++) {
8 int profit = prices[j] - prices[i];
9 if (profit > max_profit) {
10 max_profit = profit;
11 }
12 }
13 }
14 return max_profit;
15}
16
17int main() {
18 std::vector<int> prices = {7, 1, 5, 3, 6, 4};
19 std::cout << "Max Profit (Brute Force): " << maxProfit(prices) << std::endl;
20 return 0;
21}This C++ brute force solution implements two nested loops to evaluate each possible selling point for every entry price. It tracks and returns the maximum profit found among these.