Maximum Profitable Triplets With Increasing Prices I

Maximum Profitable Triplets With Increasing Prices I - Problem

Given two 0-indexed arrays prices and profits of length n. There are n items in a store where the i-th item has a price of prices[i] and a profit of profits[i].

We need to pick three items with the following condition: prices[i] < prices[j] < prices[k] where i < j < k.

If we pick items with indices i, j and k satisfying the above condition, the profit would be profits[i] + profits[j] + profits[k].

Return the maximum profit we can get, and -1 if it's not possible to pick three items with the given condition.

Input & Output

Example 1 — Basic Case

$ Input: prices = [10,20,30,40], profits = [1,4,3,7]

› Output: 14

💡 Note: We can select indices (1,2,3): prices are 20 < 30 < 40 and profits are 4+3+7=14

Example 2 — No Valid Triplet

$ Input: prices = [40,30,20,10], profits = [1,2,3,4]

› Output: -1

💡 Note: Prices are in decreasing order, so no valid triplet with increasing prices exists

Example 3 — Multiple Valid Options

$ Input: prices = [1,2,3,4,5], profits = [5,4,3,2,1]

› Output: 12

💡 Note: Best triplet is (0,1,2): prices 1 < 2 < 3, profits 5+4+3=12

Constraints

3 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁶
1 ≤ profits[i] ≤ 10⁶
prices.length == profits.length

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays: prices and profits

Find Valid Triplets

Triplets (i,j,k) where i < j < k and prices[i] < prices[j] < prices[k]

Maximize Profit

Sum profits[i] + profits[j] + profits[k]

Key Takeaway

🎯 Key Insight: For each middle element, find the maximum profit from valid left and right elements to optimize the triplet selection

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to find triplets where prices increase but maximize total profit. The optimal approach uses dynamic programming with prefix/suffix arrays to precompute maximum profits. Time: O(n²) for the practical solution, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Triplets	O(n³)	O(1)	Check every possible triplet (i,j,k) with i < j < k and prices[i] < prices[j] < prices[k]
Dynamic Programming - Prefix/Suffix Arrays	O(n)	O(n)	Precompute maximum profits for valid left and right elements using DP arrays
Optimized - Middle Element Approach	O(n²)	O(1)	For each middle element j, find maximum profit from valid left and right elements

Brute Force - Try All Triplets — Algorithm Steps

Triple nested loop through all indices i < j < k
Check if prices[i] < prices[j] < prices[k]
Track maximum profit sum among valid triplets

Visualization

Tap to expand

Step-by-Step Walkthrough

Triple Nested Loop

Try all combinations of 3 indices

Price Check

Verify prices[i] < prices[j] < prices[k]

Track Maximum

Keep track of highest profit sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* prices, int* profits, int n) {
    int maxProfit = -1;
    
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            if (prices[j] > prices[i]) {
                for (int k = j + 1; k < n; k++) {
                    if (prices[k] > prices[j]) {
                        int profit = profits[i] + profits[j] + profits[k];
                        if (profit > maxProfit) {
                            maxProfit = profit;
                        }
                    }
                }
            }
        }
    }
    
    return maxProfit;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000], profits[1000];
    int n = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 1000) {
        prices[n] = atoi(token);
        token = strtok(NULL, "[,]");
        n++;
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    for (int i = 0; i < n; i++) {
        profits[i] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(prices, profits, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops iterate through all possible triplet combinations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum profit

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler