Find Maximum Sum Triplet Array

Here's a clean, professional breakdown of the Maximum Sum Increasing Triplet (i < j < k and a[i] < a[j] < a[k]) problem and its various approaches:

Problem Statement

Given an array of positive integers of size n, find the maximum sum of a triplet (a[i], a[j], a[k]) such that:

• 0 ≤ i < j < k < n

• a[i] < a[j] < a[k]

Return the maximum possible sum of such a triplet. If no such triplet exists, return 0.

Example

Input: a[] = [2, 5, 3, 1, 4, 9]
Output: 16

Explanation:
Valid triplets with increasing values:

• 2, 3, 4 → sum = 9

• 2, 5, 9 → sum = 16

• 2, 3, 9 → sum = 14

• 3, 4, 9 → sum = 16

• 1, 4, 9 → sum = 14
  Maximum sum = 16

Naive Approach (O(n³))

Idea:

Use three nested loops and check for every triplet.

Time Complexity:

• O(n³) – not efficient for large input sizes.

Better Approach (O(n²))

Idea:

Fix the middle element a[j] and:

• Find the maximum value less than a[j] on the left → a[i]

• Find the maximum value greater than a[j] on the right → a[k]

Code:

static int maxTripletSum(int arr[], int n) {
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        int max1 = 0, max2 = 0;

        for (int j = 0; j < i; ++j)
            if (arr[j] < arr[i])
                max1 = Math.max(max1, arr[j]);

        for (int j = i + 1; j < n; ++j)
            if (arr[j] > arr[i])
                max2 = Math.max(max2, arr[j]);

        if (max1 > 0 && max2 > 0)
            ans = Math.max(ans, max1 + arr[i] + max2);
    }
    return ans;
}

Time Complexity:

• O(n²)

Space:

• O(1)

Optimized Approach (O(n log n)) using TreeSet + Suffix Array

Idea:

• Suffix Array maxSuff[i]: Stores the maximum element in the subarray from i to n-1. This gives a[k] in O(1).

• TreeSet: Stores all elements before the current index to efficiently find the largest a[i] < a[j] in O(log n) using lower().

Code:

import java.util.*;

class Solution {
    public static int maxTripletSum(int arr[], int n) {
        int[] maxSuff = new int[n + 1];
        maxSuff[n] = 0;

        // Build suffix array
        for (int i = n - 1; i >= 0; --i)
            maxSuff[i] = Math.max(maxSuff[i + 1], arr[i]);

        TreeSet<Integer> left = new TreeSet<>();
        left.add(Integer.MIN_VALUE);

        int ans = 0;

        for (int i = 0; i < n - 1; i++) {
            if (maxSuff[i + 1] > arr[i]) {
                int smaller = left.lower(arr[i]);
                if (smaller != null && smaller != Integer.MIN_VALUE) {
                    int sum = smaller + arr[i] + maxSuff[i + 1];
                    ans = Math.max(ans, sum);
                }
            }
            left.add(arr[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arr[] = { 2, 5, 3, 1, 4, 9 };
        int n = arr.length;
        System.out.println(maxTripletSum(arr, n));
    }
}

Time Complexity:

• O(n log n) due to TreeSet operations

Space Complexity:

• O(n) for suffix array and TreeSet

Summary