6
\$\begingroup\$

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<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int i = 0; i<A.Count; i++)
    {
        for (int j= A.Count-1; j>i;j--)
        {
            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum > 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<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int k = 0; k<(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 > maxSum) maxSum = sum;

    }

    return maxSum;
}

Still this exceeds time limit.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Just wondering, how fast do you want this to be, and how big of a List are we talking about? Even when checking a List of 9000 randomly generated ints the nested loop solution only takes 694 ms to run on my core i5 laptop. Also you may want to consider adding the [performance] tag and fixing your second code block. I would also recommend putting the prompt and the sample output in quote blocks instead of code blocks. \$\endgroup\$
    – jrh
    Commented May 25, 2017 at 1:12
  • \$\begingroup\$ @jrh thank you for formatting suggestions. About your question on how fast I want the code to perform, I really don't know, I thought second one is optimized solution, but I am solving questions on interviewbit.com and it says this is not the optimized solution. \$\endgroup\$ Commented May 25, 2017 at 1:18
  • \$\begingroup\$ Do you know if the question on interviewbit is focusing on algorithmic complexity (e.g., O(1) vs. O(n) vs. O(n^2)) or is it focusing on raw processing time (e.g., it must finish in 500 ms)? Are there spatial requirements (e.g., it must take up only X bytes of RAM / cannot allocate additional memory) ? \$\endgroup\$
    – jrh
    Commented May 25, 2017 at 1:22
  • \$\begingroup\$ Also is there a reason why you are using List instead of a real array (int[])? \$\endgroup\$
    – jrh
    Commented May 25, 2017 at 1:45
  • 2
    \$\begingroup\$ @jrh there are no spatial requirements. I believe they are looking at algorithmic complexity. Also I am using List because the method skeleton was already given and it had List argument. \$\endgroup\$ Commented May 25, 2017 at 2:08

2 Answers 2

6
\$\begingroup\$

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 <= 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 < 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).

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
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 < A.Length; i++)
    {
        int posi = A[i] - i;
        int negi = -A[i] - i;

        if (first || posi > bestPosi)
        {
            bestPosi = posi;
        }

        if (first || negi > 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 > best)
        {
            best = m;
        }

        first = false;
    }

    return best;
}

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

enter image description here

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.

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
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 > 0 ? 0 : A.Length - 1;
        int e = direction > 0 ? A.Length : -1;

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

            if (first || t > 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 < 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 > best)
            best = max;
    }

    return best;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thanks! Thanks for the explanation on why we can just keep track of A[i] and i. Even with the help of hints in interviewbit, I was not able to understand the logic properly. Your explanation made it clear. \$\endgroup\$ Commented May 25, 2017 at 14:12
3
\$\begingroup\$

Since j > i you can skip one call to Math.Abs

sum = Math.Abs(A[i]-A[j]) + j - i;
\$\endgroup\$
2
  • 2
    \$\begingroup\$ This really isn't a code review, it seems like it is a partial alternate solution. Can you address anything in the code to make it better? \$\endgroup\$
    – pacmaninbw
    Commented May 25, 2017 at 15:05
  • 3
    \$\begingroup\$ @pacmaninbw If skip a call to Math.Abs is not code review then what would you call it? \$\endgroup\$
    – paparazzo
    Commented May 25, 2017 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.