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).
1def maxProfit(prices):
2 min_price = float('inf')
3 max_profit = 0
4 for price in prices:
5 if price < min_price:
6 min_price = price
7 elif price - min_price > max_profit:
8 max_profit = price - min_price
9 return max_profit
10
11prices = [7, 1, 5, 3, 6, 4]
12print("Max Profit:", maxProfit(prices))This Python solution utilizes a float('inf') as an initial minimum price to ensure any price will be lower, updating min_price and max_profit accordingly during each iteration over prices.
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).
1class Solution {
2 public int maxProfit(int[] prices) {
3 int maxProfit = 0;
4 for (int i = 0; i < prices.length; i++) {
5 for (int j = i + 1; j < prices.length; j++) {
6 int profit = prices[j] - prices[i];
7 if (profit > maxProfit) {
8 maxProfit = profit;
9 }
10 }
11 }
12 return maxProfit;
13 }
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] prices = {7, 1, 5, 3, 6, 4};
17 System.out.println("Max Profit (Brute Force): " + sol.maxProfit(prices));
18 }
19}This Java implementation uses a nested loop to try every possible combination of buy and sell days, recording the highest profit obtained. This approach demonstrates the brute force search.