Solution

Method 1 – Brute Force with Three Nested Loops

Intuition

We want to find three indices i < j < k such that prices[i] < prices[j] < prices[k] and maximize profits[i] + profits[j] + profits[k]. The brute force way is to check all possible triplets.

Approach

Iterate over all possible triplets (i, j, k) with i < j < k.
For each triplet, check if prices[i] < prices[j] < prices[k].
If valid, compute the sum of profits and update the maximum.
Return the maximum profit found, or -1 if no valid triplet exists.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxProfit(vector<int>& prices, vector<int>& profits) {\n        int n = prices.size(), ans = -1;\n        for (int i = 0; i < n; ++i) {\n            for (int j = i + 1; j < n; ++j) {\n                if (prices[i] < prices[j]) {\n                    for (int k = j + 1; k < n; ++k) {\n                        if (prices[j] < prices[k]) {\n                            int sum = profits[i] + profits[j] + profits[k];\n                            if (sum > ans) ans = sum;\n                        }\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maxProfit</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> prices</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;

Related Tags