Maximum difference between sum of even and odd position elements: How to memoize the brute-force approach?

Question

I have the following code for a problem.

The problem is: Maximize the absolute difference between the sum of elements at the even and odd positions of an array. To do so, you may delete as many elements you want.

I did it by brute-force by using backtracking. My logic is that, for each index I have 2 options: a) either delete it (in this case, I put it in a set) b) don't delete it (in this case, I removed the index from the set and backtracked). I took the local maximum of two cases and updated the global maximum value appropriately.

void maxAns(vector<int> &arr, int index, set<int> &removed, int &res)
{
    if (index<0)
        return;
    int k=0;
    int s3=0,s4=0;
    for (int i=0;i<arr.size();i++)
    {
        if (i!=index)
        {
            set<int>::iterator it=removed.find(i);
            if (it==removed.end())
            {
                if( k%2==0)
                    s3+=arr[i];
                else
                    s4+=arr[i];
                k++;
            }
        }
        else    //don't delete the element
        {
            if (k%2==0)
                s3+=arr[i];
            else
                s4+=arr[i];
            k++;
        }
    }

    k=0;
    int s1=0, s2=0;
    for (int i=0;i<arr.size();i++)
    {
        if (i!=index)
        {
            set<int>::iterator it=removed.find(i);
            if (it==removed.end())
            {
                if (k%2==0)
                    s1+=arr[i];
                else
                    s2+=arr[i];
                k++;
            }
        }
        else    //delete the element
        {
            //add index into the removed set
            removed.insert(index);
        }
    }

    //delete the index element
    int t1=abs(s1-s2);
    maxAns(arr,index-1,removed,res);

    //don't delete the index element, and then backtrack
    set<int>::iterator itr=removed.find(index);
    removed.erase(itr);

    int t2=abs(s3-s4);
    maxAns(arr,index-1,removed,res);

    //choose the max value
    res=max(res,max(t1,t2));
}

Please suggest how to memoize this solution as I think it's quite inefficient. Feel free to share any interesting approach.

Answer 1

Hint: divide and conquer. Consider that a fixed length list as a left part of a larger list, maximised (or minimised) for the actual, rather than abdolute difference and depending on the parity of its length, would pair better with a right part that does not depend on the parity of its length.

[0,3] ++ [0,3]    -> diff -3 -3 = -6
[0,3] ++ [9,13,1] -> diff -3 -3 = -6

We can also easily create base cases for max_actual_diff and min_actual_diff of lists with lengths 1 and 2. Note that the best choice for those might include ommiting one or more of those few elements.

JavaScript code:

function max_diff(A, el, er, memo){
  if (memo[['mx', el, er]])
    return memo[['mx', el, er]]
  
  if (er == el)
    return memo[['mx', el, er]] = [A[el], 1, 0, 0]

  var best = [A[el], 1, 0, 0]
  
  if (er == el + 1){
    if (A[el] - A[er] > best[2]){
      best[2] = A[el] - A[er]
      best[3] = 2
    }
    if (A[er] > best[0]){
      best[0] = A[er]
      best[1] = 1
    }
    
    return memo[['mx', el, er]] = best
  }
  
  const mid = el + ((er - el) >> 1)

  const left = max_diff(A, el, mid, memo)
  const right_min = min_diff(A, mid + 1, er, memo)
  const right_max = max_diff(A, mid + 1, er, memo)
  
  // Best odd = odd + even
  if (left[0] - right_min[2] > best[0]){
    best[0] = left[0] - right_min[2]
    best[1] = left[1] + right_min[3]
  }
  // Best odd = even + odd
  if (left[2] + right_max[0] > best[0]){
    best[0] = left[2] + right_max[0]
    best[1] = left[3] + right_max[1]
  }
  
  // Best even = odd + odd
  if (left[0] - right_min[0] > best[2]){
    best[2] = left[0] - right_min[0]
    best[3] = left[1] + right_min[1]
  }
  // Best even = even + even
  if (left[2] + right_max[2] > best[2]){
    best[2] = left[2] + right_max[2]
    best[3] = left[3] + right_max[3]
  }
    
  return memo[['mx', el, er]] = best
}

function min_diff(A, el, er, memo){
  if (memo[['mn', el, er]])
    return memo[['mn', el, er]]
  
  if (er == el)
    return memo[['mn', el, er]] = [A[el], 1, 0, 0]

  var best = [A[el], 1, 0, 0]
  
  if (er == el + 1){
    if (A[el] - A[er] < best[2]){
      best[2] = A[el] - A[er]
      best[3] = 2
    }
    if (A[er] < best[0]){
      best[0] = A[er]
      best[1] = 1
    }
    
    return memo[['mn', el, er]] = best
  }
  
  const mid = el + ((er - el) >> 1)

  const left = min_diff(A, el, mid, memo)
  const right_min = min_diff(A, mid + 1, er, memo)
  const right_max = max_diff(A, mid + 1, er, memo)
  
  // Best odd = odd + even
  if (left[0] - right_max[2] < best[0]){
    best[0] = left[0] - right_max[2]
    best[1] = left[1] + right_max[3]
  }
  // Best odd = even + odd
  if (left[2] + right_min[0] < best[0]){
    best[0] = left[2] + right_min[0]
    best[1] = left[3] + right_min[1]
  }
  
  // Best even = odd + odd
  if (left[0] - right_max[0] < best[2]){
    best[2] = left[0] - right_max[0]
    best[3] = left[1] + right_max[1]
  }
  // Best even = even + even
  if (left[2] + right_min[2] < best[2]){
    best[2] = left[2] + right_min[2]
    best[3] = left[3] + right_min[3]
  }
    
  return memo[['mn', el, er]] = best
}


var memo = {}

var A = [1, 2, 3, 4, 5]
console.log(`A: ${ JSON.stringify(A) }`)
console.log(
  JSON.stringify(max_diff(A, 0, A.length-1, memo)) + ' // [odd max, len, even max, len]')
console.log(
  JSON.stringify(min_diff(A, 0, A.length-1, memo)) + ' // [odd min, len, even min, len]')
console.log('\nmemo:\n' + JSON.stringify(memo))