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 <stdio.h>
2
3int maxProfit(int* prices, int pricesSize) {
4 if (pricesSize == 0) return 0;
5 int min_price = prices[0];
6 int max_profit = 0;
7 for (int i = 1; i < pricesSize; i++) {
8 if (prices[i] < min_price) {
9 min_price = prices[i];
10 } else if (prices[i] - min_price > max_profit) {
11 max_profit = prices[i] - min_price;
12 }
13 }
14 return max_profit;
15}
16
17int main() {
18 int prices[] = {7, 1, 5, 3, 6, 4};
19 int size = sizeof(prices)/sizeof(prices[0]);
20 printf("Max Profit: %d\n", maxProfit(prices, size));
21 return 0;
22}This C solution iterates through the given prices array. It maintains the minimum price found so far and calculates potential profit as the difference between the current day's price and the tracked minimum price. The maximum of this profit value is retained.
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).
1def maxProfit(prices):
2 max_profit = 0
3 for i in range(len(prices)):
4 for j in range(i + 1, len(prices)):
5 profit = prices[j] - prices[i]
6 if profit > max_profit:
7 max_profit = profit
8 return max_profit
9
10prices = [7, 1, 5, 3, 6, 4]
11print("Max Profit (Brute Force):", maxProfit(prices))This Python brute force approach manually examines each potential sell price following every buy price, updating max_profit with the highest difference captured.