我遇到了这个算法问题。我能够实现O（n ^ 2）解决方案。在O（n）时间内有更好的方法吗？

题：

您将得到N个整数数组A1, A2 ,…, AN。返回的最大值f(i, j)为所有1 ≤ i, j ≤ N。 f(i, j)定义为|A[i] - A[j]| + |i - j|，其中|x|表示x的绝对值。

范例 ：

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

因此，我们返回5。

我的答案：

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int maxSum = 0;

        for(int i=1; i<=A.size()-1; i++){
            for(int j=i+1; j<=A.size(); j++){
                int tempSum = sum(A.get(i-1), A.get(j-1), i, j);

                if(tempSum > maxSum) {
                    maxSum = tempSum;
                }
            }
        }

        return maxSum;
    }

    public int sum(int Ai, int Aj, int i, int j) {
        return Math.abs(Ai-Aj) + Math.abs(i-j);
    }
}

同样在我的解决方案中，内部循环从i +1到N，因此最坏的情况是该循环为N-1。我的整体解决方案仍然是O（n ^ 2）吗？