122. Best Time to Buy and Sell Stock II

This problem asks to find the maximum profit achievable by buying and selling a stock multiple times, given an array of stock prices for each day. You can hold at most one share at a time, but you can buy and sell on the same day.

Approach 1: Greedy Algorithm

This is the most efficient approach. The core idea is to buy on every day when the price is lower than the next day's price and sell on the next day. This leverages all the increasing trends in the price sequence.

Algorithm:

1. Iterate through the prices array starting from the second element.
2. For each element, compare it to the previous element.
3. If the current element is greater than the previous element, it implies a price increase. Add the difference (profit) to the total profit.
4. Continue iterating until the end of the array.
5. Return the total profit.

Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once. Space Complexity: O(1), as we use only a constant amount of extra space.

Code Implementation (Python):

def maxProfit(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit
 

Code Implementation (Java):

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}

Code Implementation (C++):

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        for (size_t i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
};

Approach 2: Dynamic Programming (More complex, less efficient)

While dynamic programming can solve this, it's less efficient than the greedy approach. It's included here for completeness to show a different approach. It adds unnecessary complexity for this problem.

Algorithm: This approach uses a 2D DP array dp[i][j] where i represents the day and j represents whether we hold a stock (0 for holding, 1 for not holding). The recurrence relation is:

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) (Hold or buy)
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) (Hold or sell)

The final answer will be dp[n-1][1].

Time Complexity: O(n) Space Complexity: O(n) (can be optimized to O(1) by keeping track of only the previous day's values)

Code Implementation (Python - less efficient DP):

def maxProfitDP(prices):
    n = len(prices)
    dp = [[0, 0] for _ in range(n)]
    dp[0][0] = -prices[0]  #initial state
    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
    return dp[n - 1][1]

Note: The space-optimized DP version (O(1) space) is generally similar to the greedy solution in terms of code structure and efficiency and is therefore omitted for brevity. The greedy approach is simpler and preferred for this problem.