arrays - 最大化可以由数组形成的所有非重叠子数组的最大和最小元素之间的绝对差之和?
问题描述
例如: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
解决方案
我们可以有一个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.");
推荐阅读
- reactjs - 从 React 应用程序向 pm2 启动的 Express 服务器发出请求时出现“原因:CORS 请求未成功”
- python - 从目录中读取多个 CSV 文件以检查列数
- events - 如何检查或检测窗口是否在 SDL 中最小化或不活动?
- python - 我想使用for循环在python中的字典中获取每个主题的总和
- android - 自定义视图从Android中的自定义主题属性获取自定义属性值
- javascript - Ramda - 然后,否则,andFinally?
- c# - 来自主 m3u8 文件的高带宽正则表达式匹配分辨率
- typescript - 如何在 TypeScript 中声明全局类型别名?
- javascript - 已安装不可变但仍显示未定义
- angular - 如何解决 jasmin UNIT 测试用例中的这种奇怪的随机错误?