建议把那些已婚但还在公司做同事情侣的人优先处理掉，真是道德败坏

先把题目翻成大白话：给你一个数组，要找三个下标 i<j<k，而且数值满足 a[i] < a[j] < a[k]，让三者的和尽量大。找不到就说没有。你看，限制其实就两条：顺序要对，数要递增。

直觉与坑点

最直接的想法是三重循环全试一遍，时间 O(n³)，小数据还能跑，大一点就卡死。更“聪明”的思路是换个角度：定住中间那个 a[j]，只需要知道：

• 左边有没有比 a[j] 小的里最大的那个；
• 右边有没有比 a[j] 大的里最大的那个。 这俩一凑，a[i]+a[j]+a[k] 就定了。关键在于“最大的小于它”和“最大的大于它”，听着矛盾，其实数据结构能帮忙。

数据结构怎么用

左边部分：一路从左往右扫，用一个有序集合存已经路过的数。对当前 a[j]，想要左边最大且 < a[j]，在 Java 里 TreeSet 的 lower(x) 恰好给“严格小于 x 的最大元素”。 右边部分：为了获得右边“严格大于 a[j] 的最大元素”，从右往左再扫一遍也行，但更省事的是先做一次预处理：从右往左维护一个 TreeSet，记录“到当前为止右边所有见过的数的最大值”。如果这个最大值都不大于 a[j]，那 a[j] 右边就没救了；否则这个最大值就是我们要的 k 值（因为我们只关心右侧里最大的且比它大，最大值若大于它就成立）。

这样整体是两趟扫描 + 若干次对 TreeSet 的 add/lower/last 查询，复杂度 O(n log n)，空间 O(n)。

边界与细节

• 数组里有重复？没事，条件是严格递增，用 lower 保证 <，右边用“最大值>当前值”保证 >。
• 可能有负数？不影响，比较和大小关系照样成立。
• 只要有任一侧找不到合适的数，就跳过该 j。

代码（Java）

import java.util.*;

publicclassMaxIncreasingTripletSum{

staticclassTriplet{
int i, j, k;
long sum;
        Triplet(int i, int j, int k, long sum) {
this.i = i; this.j = j; this.k = k; this.sum = sum;
        }
@Overridepublic String toString(){
return String.format("indices=(%d,%d,%d), values sum=%d", i, j, k, sum);
        }
    }

publicstatic Triplet maxSumIncreasingTriplet(int[] a){
int n = a.length;
if (n < 3) returnnull;

// 预处理：rightMaxGreaterVal[j] 记录在 j 右侧中 “最大且 > a[j] 的值”；若不存在为 null
        Integer[] rightMaxGreaterVal = new Integer[n];
// 同时记录该最大值的下标，方便输出三元组位置
int[] rightMaxGreaterIdx = newint[n];
        Arrays.fill(rightMaxGreaterIdx, -1);

        TreeSet<Integer> rightSet = new TreeSet<>();
int currentRightMax = Integer.MIN_VALUE;

for (int j = n - 1; j >= 0; j--) {
if (!rightSet.isEmpty() && currentRightMax > a[j]) {
                rightMaxGreaterVal[j] = currentRightMax;
// 为了找 index，需要知道这个最大值的具体位置；我们可以先扫一遍右边建立“值->最右下标”
            } else {
                rightMaxGreaterVal[j] = null;
            }
            rightSet.add(a[j]);
if (a[j] > currentRightMax) currentRightMax = a[j];
        }

// 值可能重复，建一个“值 -> 最右出现位置”的映射，保证取到合法且在右侧的下标
        Map<Integer, Integer> lastIndex = new HashMap<>();
for (int idx = 0; idx < n; idx++) lastIndex.put(a[idx], idx);
for (int j = 0; j < n; j++) {
if (rightMaxGreaterVal[j] != null) {
int val = rightMaxGreaterVal[j];
int idx = lastIndex.get(val);
                rightMaxGreaterIdx[j] = (idx > j) ? idx : -1; // 保险起见
            }
        }

// 左侧用 TreeSet，lower(x) 拿到严格小于 x 的最大值；同时需要它的下标
        TreeSet<Integer> leftSet = new TreeSet<>();
// 对于“值 -> 最右下标”，但这是左侧扫描，随扫随记即可
        Map<Integer, Integer> latestLeftIndex = new HashMap<>();

        Triplet best = null;

for (int j = 0; j < n; j++) {
            Integer leftVal = leftSet.lower(a[j]); // 左侧最大且小于 a[j]
int leftIdx = -1;
if (leftVal != null) {
// latestLeftIndex 里存的是到当前为止该值最后一次出现的位置，必然 < j
                leftIdx = latestLeftIndex.get(leftVal);
            }

int rightIdx = rightMaxGreaterIdx[j];

if (leftVal != null && rightIdx != -1) {
long sum = (long) leftVal + a[j] + a[rightIdx];
if (best == null || sum > best.sum) {
                    best = new Triplet(leftIdx, j, rightIdx, sum);
                }
            }

// 扫描推进：把当前值纳入左侧集合与索引
            leftSet.add(a[j]);
            latestLeftIndex.put(a[j], j);
        }

return best;
    }

// 简单演示
publicstaticvoidmain(String[] args){
int[] arr = {2, 5, 3, 1, 4, 9};
        Triplet ans = maxSumIncreasingTriplet(arr);
        System.out.println(ans == null ? "No valid triplet" : ans);
    }
}

把 j 定住，相当于把三元组拆成“左最大且更小”和“右最大且更大”，分别用 lower 和“看右侧最大值是否大过自己”就能判断与取值。因为我们总是拿左右两侧在条件允许下的最大值，拼出来的和自然就是以 j 为中心的最优；对所有 j 取最大，就得到全局最优。复杂度 O(n log n)，能撑很大的 n。你要是想再挤点性能，可以把右侧的“最大大于它”用后缀最大数组+单调性判断来做，但 TreeSet 已经够稳。好了，差不多就这样。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html