2921. Maximum Profitable Triplets With Increasing Prices II

Let's fix the middle chosen item for instance index j.

Let’s define an array max_right, where max_right[j] represents the maximum profit[k] for every index k > j such that prices[k] > prices[j].

Consider using a Fenwick tree to fill the max_right.

Do the same for items with an index i < j such that prices[i] < prices[j] and find the maximum profit[i] among them. Let's call this array max_left.

Now the profit when an item with the index j is the middle one would be profit[j] + max_right[j] + max_left[j].

Finally, do the above procedure for all j's and find the maximum profit among them. That would be the final answer.