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

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

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

Maximize the sum of absolute difference between max and min elements of all non overlapping sub-arrays that can be formed from an array?

arrays

algorithm

greedy