arrays - 最大化可以从数组形成的所有非重叠子数组的最大和最小元素之间的绝对差之和？

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

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.");