Maximum absolute difference of array elements I am trying to solve a question from array section:


  You are given an array of N integers, A1, A2 ,…, AN. Return maximum
  value of f(i, j) for all 1 ≤ i, j ≤ N.
        f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.
  
  For example

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

  
  So, we return 5.


I solved the problem correctly, however my solution is not the optimized one. Here is my solution:

public int maxArr(List&lt;int&gt; A) {
    if (A==null || A.Count&lt;=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int i = 0; i&lt;A.Count; i++)
    {
        for (int j= A.Count-1; j&gt;i;j--)
        {
            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum &gt; maxSum) maxSum = sum;
        }
    }

    return maxSum;
}


So I understand with bigger lists or arrays nested loops might not be a good idea, but what can I do to optimize this solution? 

Update: I also tried removing nested loops 

public int maxArr(List&lt;int&gt; A) {
    if (A==null || A.Count&lt;=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int k = 0; k&lt;(A.Count)*(A.Count); k++)
    {
        int i = k/A.Count;
        int j = k%A.Count;

            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum &gt; maxSum) maxSum = sum;

    }

    return maxSum;
}


Still this exceeds time limit.
There is a (simple) linear time (and by necessity space) solution. My thanks to 'random person next to me' for being a Rubber Duck in this process.

It's really very simple: observe that |Ai - Aj| + |i - j| is just the maximum of 4 other functions: + Ai + i - Aj - j, + Ai - i - Aj + j, - Ai + i + Aj - j, - Ai - i + Aj + j.

Knowing this, we can compute one half of each of these (e.g. + Ai + i) for each value in linear time and store them in an array. Now the half-clever bit is this: if we 'look' at point j, we know that if our best partner (i) is to the left of us (i.e. i &lt;= j) that it is the i to the left of us with either the largest + Ai + i or - Ai - i, to which we will add - Aj - j or + Aj - j to compute the result. The same is true for the j to our left, (excluding our current j), and for the j next to him, etc. This means we can compute the 'best' is for the js to their right all at the same time (linear) and then just look them up when we compare them to each j. The same can be said for j &lt; i.

Duly, we can compute 4 arrays, one for each of the 4 functions that we need to find the maximum of, but only containing the Ai and i components, and replace any element smaller than any element to the right (or left) with the greatest element to it's right (or left):

With these 4 arrays built (in linear time) we can loop through the array, computing the other half (e.g. - Aj - j) and find the max of adding each half to it's corresponding other half. Our solution is then just the max of these sums.

In actuality, this can be implemented very cleanly as just 1 pass over the original array, where we keep track of the largest + Ai + i and - Ai + i, and compare it to the current Aj and j sums (we can argue from symmetry that going the other way is pointless - we know that the optimal has a 'left' and a 'right', we only need to look at one of them).



/// &lt;summary&gt;
/// Finds the max of |Ai - Aj| + |i - j|
/// &lt;/summary&gt;
/// &lt;param name="A"&gt;The array of Ai&lt;/param&gt;
/// &lt;returns&gt;The max of |Ai - Aj| + |i - j|&lt;/returns&gt;
public static int SimpleSuperiorMaxArr(int[] A)
{
    int best = 0; // known lower bound

    int bestPosi = 0;
    int bestNegi = 0;
    bool first = true;

    for (int i = 0; i &lt; A.Length; i++)
    {
        int posi = A[i] - i;
        int negi = -A[i] - i;

        if (first || posi &gt; bestPosi)
        {
            bestPosi = posi;
        }

        if (first || negi &gt; bestNegi)
        {
            bestNegi = negi;
        }

        int posj = -A[i] + i;
        int negj = A[i] + i;

        int pos = bestPosi + posj;
        int neg = bestNegi + negj;

        int m = Math.Max(pos, neg);

        if (m &gt; best)
        {
            best = m;
        }

        first = false;
    }

    return best;
}


owing to the algorithms simplicity, we can implement it in Excel without any trouble at all!



All of the functions are as on the left, with the 'best' rows being the max of the current value and the previous (or just current for the first column). Note that it works left-to-right, so the 'best' rows never decrease in value to the right. The 'ans' is just the max of all of the bottom pair of rows.

Edit: old code kept for posterity:

This code isn't the highest quality code ever, but it seems to work.

/// &lt;summary&gt;
/// Finds the max of |Ai - Aj| + |i - j|
/// &lt;/summary&gt;
/// &lt;param name="A"&gt;The array of Ai&lt;/param&gt;
/// &lt;returns&gt;The max of |Ai - Aj| + |i - j|&lt;/returns&gt;
public static int SuperiorMaxArr(int[] A)
{
    // Computes the array of Ai * ac + i * ic
    int[] ComputeInfoArray(int ac, int ic) // for our case, ic and direction are equal
    {
        int direction = -ic; // if we are adding i, then we are the 'right' array, otherwise we are 'left' array
        int[] iarr = new int[A.Length];

        bool first = true;
        int b = 0; // current best

        int s = direction &gt; 0 ? 0 : A.Length - 1;
        int e = direction &gt; 0 ? A.Length : -1;

        for (int i = s; i != e; i += direction)
        {
            int t = A[i] * ac + i * ic;

            if (first || t &gt; b)
            {
                first = false;
                b = t;
            }

            iarr[i] = b;
        }

        return iarr;
    }

    int[] LeftLow = ComputeInfoArray(1, -1); // + Ai - i
    int[] LeftHigh = ComputeInfoArray(-1, -1); // - Ai - i
    int[] RightLow = ComputeInfoArray(1, 1); // + Ai + i
    int[] RightHigh = ComputeInfoArray(-1, 1); // - Ai + i

    int best = 0; // known lower bound

    for (int j = 0; j &lt; A.Length; j++)
    {
        int ll = LeftLow[j] + j - A[j];
        int lh = LeftHigh[j] + j + A[j];
        int rl = RightLow[j] - j - A[j];
        int rh = RightHigh[j] - j + A[j];

        // in truth, we can just compute ll + lh

        int max = Math.Max(Math.Max(ll, lh), Math.Max(rl, rh));

        if (max &gt; best)
            best = max;
    }

    return best;
}