求满足0≤P≤Q<N的(A[Q]+A[P]+Q-P)最大值的Java解法

首先，我们需要对目标表达式做关键变形，这是实现线性时间复杂度的核心：

原式：A[Q] + A[P] + Q - P（其中 0 ≤ P ≤ Q < N）

可以拆分为：(A[Q] + Q) + (A[P] - P)

为什么要这么拆？因为当我们固定Q时，A[Q]+Q是确定值，此时只需要找到所有P ≤ Q中A[P]-P的最大值，两者相加就是当前Q对应的最大可能值；遍历所有Q后，全局的最大值就是答案。

或者反过来，也可以拆成(A[P] + P) + (A[Q] - Q)，对应从后往前遍历的思路，两种方式都能达到O(N)时间、O(1)空间的要求。

方式一：从前往后遍历（更直观） #

思路 #

1. 初始化maxAPMinusP为A[0] - 0（即第一个元素的A[P]-P值）
2. 初始化maxResult为2 * A[0]（对应初始情况P=Q=0）
3. 从索引1开始遍历每个Q：
   • 计算当前Q对应的currentVal = (A[Q] + Q) + maxAPMinusP
   • 更新maxResult为当前全局最大值
   • 更新maxAPMinusP为max(maxAPMinusP, A[Q]-Q)（当前Q可以作为后续遍历的P候选）

Java实现代码 #

public class MaxValueCalculator {
    public static int findMaxValue(int[] A) {
        if (A == null || A.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        int maxAPMinusP = A[0] - 0;
        int maxResult = 2 * A[0]; // P=Q=0的初始情况
        
        for (int q = 1; q < A.length; q++) {
            int currentVal = (A[q] + q) + maxAPMinusP;
            maxResult = Math.max(maxResult, currentVal);
            // 更新最大的A[P]-P，当前q可作为后续的P
            maxAPMinusP = Math.max(maxAPMinusP, A[q] - q);
        }
        return maxResult;
    }

    public static void main(String[] args) {
        int[] a = new int[] {3,5,2,1,2};
        System.out.println(findMaxValue(a)); // 输出：10
    }
}

方式二：从后往前遍历（对应你提供的部分代码思路） #

思路 #

我们也可以把原式拆成(A[P] + P) + (A[Q] - Q)，此时固定P，找Q ≥ P中A[Q]-Q的最大值，两者相加就是当前P对应的最大可能值。

1. 初始化maxAQMinusQ为A[N-1] - (N-1)（最后一个元素的A[Q]-Q值）
2. 初始化maxResult为2*A[N-1]（对应P=Q=N-1的情况）
3. 从索引N-2开始往前遍历每个P：
   • 计算当前P对应的currentVal = (A[P] + P) + maxAQMinusQ
   • 更新maxResult为当前全局最大值
   • 更新maxAQMinusQ为max(maxAQMinusQ, A[P]-P)（当前P可以作为后续Q的候选）

修正你提供的部分代码 #

你给出的代码存在几个问题：

• 变量p未定义，循环变量q实际应该是遍历P的索引
• max_q的初始化错误，应该是A[length-1] - (length-1)，而非单纯的A[length-1]
• 缺少对max_q的更新逻辑

修正后的完整代码：

public static int findMaxValueFromReverse(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException("数组不能为空");
    }
    int n = A.length;
    int maxAQMinusQ = A[n-1] - (n-1);
    int result = 2 * A[n-1]; // P=Q=n-1的初始情况
    
    for (int p = n-2; p >= 0; p--) {
        int currentVal = (A[p] + p) + maxAQMinusQ;
        result = Math.max(result, currentVal);
        // 更新最大的A[Q]-Q，当前p可作为后续的Q
        maxAQMinusQ = Math.max(maxAQMinusQ, A[p] - p);
    }
    return result;
}

关键说明 #

• 两种方式都严格满足O(N)时间复杂度（仅一次遍历）和O(1)空间复杂度（仅用了几个额外变量）
• 必须处理数组为空的边界情况，避免空指针或逻辑错误
• 表达式变形是核心，通过拆分把二维遍历问题（所有P和Q组合）降为一维问题（维护单个最大值）

内容的提问来源于stack exchange，提问作者Reddy Stark