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).
1class Solution {
2 public int maxProfit(int[] prices) {
3 if (prices.length == 0) return 0;
4 int minPrice = Integer.MAX_VALUE;
5 int maxProfit = 0;
6 for (int price : prices) {
7 if (price < minPrice) {
8 minPrice = price;
9 } else if (price - minPrice > maxProfit) {
10 maxProfit = price - minPrice;
11 }
12 }
13 return maxProfit;
14 }
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] prices = {7, 1, 5, 3, 6, 4};
18 System.out.println("Max Profit: " + sol.maxProfit(prices));
19 }
20}In this Java solution, we iterate over each price in the array, keeping track of the lowest price observed so far. The potential profit for each day is calculated, and the maximum profit is updated if the current potential profit is greater.
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 <stdio.h>
2
3int maxProfit(int* prices, int pricesSize) {
4 int max_profit = 0;
5 for (int i = 0; i < pricesSize; i++) {
6 for (int j = i+1; j < pricesSize; j++) {
7 int profit = prices[j] - prices[i];
8 if (profit > max_profit) {
9 max_profit = profit;
10 }
11 }
12 }
13 return max_profit;
14}
15
16int main() {
17 int prices[] = {7, 1, 5, 3, 6, 4};
18 int size = sizeof(prices)/sizeof(prices[0]);
19 printf("Max Profit (Brute Force): %d\n", maxProfit(prices, size));
20 return 0;
21}This C implementation uses nested loops to check all possible buy and sell day pairs, computing the profit and tracking the highest encountered. It serves as an illustration of the brute force method.