偶数和奇数位置元素之和之间的最大差异：如何记住蛮力方法？

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

Answer 2

最大化数组奇数和偶数位置元素之和的绝对差值。为此，您可以删除任意数量的元素。

例子

A = [9, 5, 2, 9, 4]

答案 = 16 => [9, 2, 9] = 9-2+9

A = [8, 6, 2, 7, 7, 2, 7]

答案 = 18 => [8, 2, 7, 2, 7] = 8-2+7-2+7

提示：

在"i+1"位置，令子数组A[i+1,n]的所有子序列的最大可能差和最小可能差分别为Max，Min
因此在位置"i"，子数组A[i, n]的所有子序列的最大和最小可能差可以计算为

包含当前元素arr[i]
不包含当前元素arr[I]

Max = MAX(Max, arr[i] - Min) 
Min = MIN(Min, arr[i] - Max)

解释：

A      =   9, 5, 2, 9, 4 
Max    =  16, 12, 9, 9, 4 
Min    =  -7, -7, -7, 0, 0

最终答案：Max(Max[0], Min[0]) = Max(16, -7) = 16

时间复杂度： O(n)

Space 复杂度： O(1) * 因为只使用了 2 个变量 Max、Min*

Answer 3

假设我们总是在偶数位置添加值，而我们总是在奇数位置保留值。现在，我们将从 1 迭代到 n 并做出选择：保留元素或删除它；问题是当我们保留一个元素时，我们需要知道它是在偶数位置还是奇数位置，所以我们将进行动态规划： [][0]dp[i][0]：使用 1,2,...,a1,a2,...,ai 中元素的最大可能总和，所得数组的长度为偶数。 [][1]dp[i][1]：与上面相同，但现在结果数组的长度为奇数。过渡是：保留它或删除它。 [][]=max([−1][],[−1][!]+[]∗((==0)?1:−1)dp[i][r]=max(dp[i −1][r],dp[i−1][!r]+a[i]∗((r==0)?1:−1); 现在是有人说：等一下，你总是在偶数位置添加并在奇数位置休息，如果它是另一种方式怎么办。那么，为此，再次执行 DP，但在奇数位置添加并在偶数位置休息。您选择两种解决方案中的最大值

偶数和奇数位置元素之和之间的最大差异：如何记住蛮力方法？

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

c++

algorithm

dynamic-programming

backtracking

memoization