title: Maximum absolute difference in an array
body: <p>I came across this algorithm question. I was able to implement a O(n^2) solution. Is there a better way of doing this in O(n) time? </p>
  
  <p><strong>Question:</strong></p>
  
  <p>You are given an array of N integers, <code>A1, A2 ,…, AN</code>. Return maximum value of <code>f(i, j)</code> for all <code>1 ≤ i, j ≤ N</code>.
  <code>f(i, j)</code> is defined as <code>|A[i] - A[j]| + |i - j|</code>, where <code>|x|</code> denotes absolute value of x.</p>
  
  <p><strong>Example</strong>:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>So, we return 5.</p>
  
  <p><strong>My Answer:</strong></p>
  
  <pre><code>public class Solution {
      public int maxArr(ArrayList&lt;Integer&gt; A) {
          int maxSum = 0;
  
          for(int i=1; i&lt;=A.size()-1; i++){
              for(int j=i+1; j&lt;=A.size(); j++){
                  int tempSum = sum(A.get(i-1), A.get(j-1), i, j);
  
                  if(tempSum &gt; 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);
      }
  }
  </code></pre>
  
  <p>Also in my solution the inner loop runs from i + 1 to N, so the worst case is N-1 for that loop. Is my overall solution still O(n^2)?</p>