c++ - 偶数和奇数位置元素之和的最大差值 : How to memoize the brute-force approach?

Question

我有以下代码来解决一个问题。

问题是: 最大化数组奇数和偶数位置元素之和的绝对差。 为此，您可以删除您想要多少元素。

我是通过使用回溯法通过蛮力完成的。我的逻辑是，对于每个索引，我有 2 个选项: a) 要么删除它(在这种情况下，我把它放在一个集合中) b) 不要删除它(在这种情况下，我从集合中删除索引并回溯)。 我取了两种情况的局部最大值并适本地更新了全局最大值。

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));
}

请建议如何内存这个解决方案，因为我认为它效率很低。欢迎分享任何有趣的方法。

Answer 1

提示:分而治之。考虑一个固定长度的列表作为一个更大列表的左侧部分，最大化(或最小化)实际的，而不是绝对差异并且取决于其长度的奇偶校验，将更好地与不依赖于的右侧部分配对其长度的奇偶校验。

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

我们还可以轻松地为长度为 1 和 2 的列表的 max_actual_diff 和 min_actual_diff 创建基本情况。请注意，对这些情况的最佳选择可能包括省略一个或多个那几个元素。

JavaScript 代码:

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