Problem Explanation

You are given an array of integers where each integer represents the price of a stock on a particular day. Your goal is to find and return the maximum profit you could possibly achieve. You may engage in as many "buy and sell" transactions as you want. However, you cannot engage in multiple transactions at the same time, meaning you cannot buy stock again before selling the stock you currently have.

Let's take an example:

Input: [7, 1, 5, 3, 6, 4]

For maximum profit, we would buy the stock when the cost is lowest and sell it when the cost is highest. Taking this into account, we could buy on day 2 (price = 1) and sell on day 3 (price = 5), giving us a profit of 5 - 1 = 4. Then, we could buy again on day 4 (price = 3) and sell on day 5 (price = 6), giving us another profit of 6 - 3 = 3. Therefore, the total profit would be 4 + 3 = 7.

Algorithm

We can solve this problem using a Greedy Approach. This approach is based on the premise of making locally optimal choices at each stage with the hope that these choices would lead us to a globally optimal solution.

We iterate over the prices array and calculate the maximum profit we can achieve. For each day, we maintain two variables: sell and hold. sell is the maximum profit we can make if we sell the stock that day, and hold is the maximum profit we could have made, up to that day, by buying or holding the stock.

Whenever we meet a price that is greater than the previous price, we will update the sell variable by adding the increment to the sell variable. If the current price is less than the previous price, the increment will become negative and will decrease the sell variable, which is consistent with our intention to maximize the profit.

The hold variable, on the other hand, maintains the maximum profit we can make by holding, or by not selling the stock at that day. It is calculated as the maximum between current hold and sell - price.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int maxProfit(vector<int>& prices) {
6    int sell = 0; // the maximum profit we can make by selling the stock
7    int hold = INT_MIN; // the maximum profit we can make by holding the stock
8
9    // iterate through the prices array
10    for (const int price : prices) {
11      // calculate the maximum profit by selling the stock that day
12      sell = max(sell, hold + price);
13      // calculate the maximum profit we can make by holding the stock
14      hold = max(hold, sell - price);
15    }
16
17    // return the maximum profit
18    return sell;
19  }
20};

This C++ Solution has a time complexity of O(n) where n is the size of the prices array. This is because we iterate once over the array.

Python Solution

1
2python
3class Solution:
4    def maxProfit(self, prices):
5        sell, hold = 0, float('-inf')
6        for price in prices:
7            sell, hold = max(sell, hold + price), max(hold, sell - price)
8        return sell

Java Solution

1
2java
3import java.lang.Math;
4
5public class Solution {
6    public int maxProfit(int[] prices) {
7        int sell = 0, hold = Integer.MIN_VALUE;
8        for (int price : prices) {
9            sell = Math.max(sell, hold + price);
10            hold = Math.max(hold, sell - price);
11        }
12        return sell;
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4    maxProfit(prices) {
5        let sell = 0, hold = Number.NEGATIVE_INFINITY;
6        for (let price of prices) {
7            [sell, hold] = [Math.max(sell, hold + price), Math.max(hold, sell - price)];
8        }
9        return sell;
10    }
11}

C# Solution

1
2csharp
3public class Solution {
4    public int MaxProfit(int[] prices) {
5        int sell = 0, hold = Int32.MinValue;
6        foreach (int price in prices) {
7            sell = Math.Max(sell, hold + price);
8            hold = Math.Max(hold, sell - price);
9        }
10        return sell;
11    }
12}

In this approach, every day we decide to either continue to hold the stock or to sell the stock (with the addition price in hand), resulting in the maximum profit. At the end of the loop, we are not holding any stock, and the value of sell represents the maximum profit. The above solutions solve the problem using O(1) extra space and linear time complexity. All the solutions follow the greedy approach and maintain two variables at each step to keep track of the maximum profit by either selling or holding the stock.

The time complexity of these solutions is O(n), where n is the size of the prices array. The space complexity is O(1) since only two variables are used. This is highly efficient, especially for large input arrays.

All the solutions are easy to understand and implement. Each day you check whether it would be more profitable to sell the stock (factoring in the price you could buy it back for today) or hold onto the stock and wait for potentially higher future prices. At the end of this, the 'sell' variable will represent the maximum profit you can make.

It's important to note that the Python, JavaScript and C# solutions use the built-in max() function to calculate the maximum profit that can be made by holding or selling the stock. In contrast, the Java Solution uses Math.max() to achieve the same result.

In conclusion, this problem demonstrates the practical usage of the Greedy approach in order to arrive at an optimal solution. This concept has wide applications in various real-world scenarios, such as stock market analysis, resource allocation, and many others.