LeetCode 2921: Maximum Profitable Triplets With Increasing Prices II

Explanation:

To solve this problem, we can iterate through the given prices array and keep track of the maximum profit that can be obtained by considering three elements (triplets) in increasing order. We maintain three variables to store the maximum profit that can be obtained by considering each triplet ending at the current index.

1. Initialize three variables first, second, and third to store the maximum profit for the first, second, and third element of the triplet ending at the current index.
2. Iterate through the prices array and update these variables based on the current price.
3. At each index i, we update the first, second, and third values as follows:
   • first = max(first, -price[i]) (max profit if the first element is at index i)
   • second = max(second, first + price[i]) (max profit if the second element is at index i)
   • third = max(third, second - price[i]) (max profit if the third element is at index i)
4. After iterating through the prices array, the maximum profit will be stored in the third variable.

Time Complexity: O(N), where N is the number of elements in the prices array. Space Complexity: O(1)

:

class Solution {
    public int maxProfit(int[] prices) {
        int first = Integer.MIN_VALUE, second = 0, third = 0;
        
        for (int price : prices) {
            first = Math.max(first, -price);
            second = Math.max(second, first + price);
            third = Math.max(third, second - price);
        }
        
        return third;
    }
}