如何最大化由数组中所有不重叠子数组的最大元素和最小元素的绝对差的总和？

Question

例如: A = [2, 3, 0, 1, 5]

现在A可以被分成多个子数组 一种方法是：A ~ [2], [3, 0], [1, 5]

现在可以从一个数组中形成的所有不重叠子数组的最大和与最小元素的绝对差之和为：

=> max([2]) - min([2]) + max([3, 0]) - min([3, 0]) + max([5, 1]) - min([5, 1]) 
=> 2 - 2 + 3 - 0 + 5 - 1
=> 7

问题的限制条件：

1 <= length of array <= 10^6

-10^9 <= A[i] <= 10^9

- Utkarsh Sharma

---

在你的例子中，子数组的长度为1或2。这是一个限制条件还是只是一个例子？ - Damien

@Damien 我认为问题是如何最好地划分数组。 - גלעד ברקן

所有元素都不同吗？ - AKSingh

@AKSingh 数组中可能存在重复元素。 - Utkarsh Sharma

我已经发布了一个贪心算法解决方案来解决你的问题。然而，它并不适用于重复项。在重复项的情况下，需要更新解决方案。 - AKSingh

Answer 1

我们可以使用一个O(n)的动态规划程序。让我们为每个元素保存三个状态：

1. best_sum_if_highest

2. best_sum_if_lowest

3. best_sum_if_neither

在每次迭代中，一个元素可以(1)扩展早期、较低或相等元素的范围，如果它是一个部分的最高点，(2)扩展早期、较高或相等元素的范围，如果它是一个部分的最低点，或者(3)不对总和做出贡献。

请注意，(1)和(2)是互斥的，因为如果最后一个不同的早期元素更高，那么该元素无法满足(1)，反之亦然。

让我们假设我们将超过两个连续相同元素的序列合并到最大为二，因为额外的元素无法做出贡献。

动态规划:

// Extend lower highest
dp[i][0] = A[i] - A[i-1] + max(dp[i-1][0], dp[i-1][2])
  if A[i-1] ≤ A[i]
  
// Extend higher lowest
dp[i][1] = A[i-1] - A[i] + max(dp[i-1][1], dp[i-1][2])
  if A[i-1] ≥ A[i]
  
// Don't contribute
dp[i][2] = max(
  dp[i-1][0],
  dp[i-1][1],
  dp[i-1][2]
)

例子 1：

[2, 3, 0, 1, 5]

A[i]  states 
2     [0, 0, 0]
3     [1, 0, 0]
0     [0, 3, 1]
1     [2, 0, 3]
5     [7, 0, 3]

示例 2：

[1, 5, 2, 1, 6, 0, 7]

A[i]  states 
1     [0,  0,  0]
5     [4,  0,  0]
2     [0,  3,  4]
1     [0,  5,  4]
6     [9,  0,  5]
0     [0, 14,  9]
7     [16, 0, 14]

使用随机比较的JavaScript代码，与暴力破解（好吧，至少是朴素的O(n^2)）进行比较：

function f(A){
  const dp = new Array(A.length);
  
  for (let i=0; i<A.length; i++)
    dp[i] = [0, 0, 0];
  
  for (let i=1; i<A.length; i++){
    if (A[i] >= A[i-1]){
      dp[i][0] = A[i] - A[i-1] + Math.max(dp[i-1][0], dp[i-1][2]);
      dp[i][1] = 0;
    }
    
    if (A[i] <= A[i-1]){
      dp[i][0] = 0;
      dp[i][1] = A[i-1] - A[i] + Math.max(dp[i-1][1], dp[i-1][2]);
    }
    
    dp[i][2] = Math.max(...dp[i-1]);
  }
  
  return Math.max(...dp[A.length - 1]);
}


function bruteForce(A){
  const dp = new Array(A.length);
  
  dp[0] = 0;
  dp[-1] = 0;
  
  for (let i=1; i<A.length; i++){
    let min = A[i];
    let max = A[i];
    let best = dp[i-1];
    
    for (let j=i-1; j>=0; j--){
      min = Math.min(min, A[j]);
      max = Math.max(max, A[j]);
      best = Math.max(best, max - min + dp[j-1]);
    }
    
    dp[i] = best;
  }
  
  return dp[A.length - 1];
}

var numTests = 1000;

for (let i=0; i<numTests; i++){
  const N = 10;
  const A = [];
  const n = 50;
  for (let j=0; j<n; j++){
    const num = Math.floor(Math.random() * (1 << N));
    A.push(num);
  }

  const fA = f(A);
  const brute = bruteForce(A);

  if (fA != brute){
    console.log('Mismatch:');
    console.log(A);
    console.log(fA, brute);
    console.log('');
  }
}

console.log("Done testing.");

- גלעד ברקן