数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 |arr[i] – arr[j] - + |i – j| 的最大值
在这个问题中，我们给定一个包含 n 个整数的数组。我们的任务是创建一个程序，找到 |arr[i]-arr[j]| + |i-j| 的最大值。
让我们举个例子来理解这个问题，
输入 − array = {4, 1, 2}
输出 − 4
解释 −
|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4 |arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4 |arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2
为了解决这个问题，一个简单的办法是使用暴力法，它会使用两个循环并找到最大差值。
但是一个更有效的办法是使用绝对函数的性质，
让我们解码方程式并找到解决方案，
arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}第一个和第四个是一样的，第二个和第四个是一样的。利用这一点，我们将创建两个数组，分别存储值 arr[i]+- i。
array1 将存储值 arr[i] + i
array2 将存储值 arr[i] - i
所以，我们将找到两个值的较大值，即
max ((max(array1)-min(array1)), (max(array2)-min(array2)))
示例
程序展示了我们解决方案的实现，
#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
return ans;
}
int main() {
int array[] = { 5, 7, 1, 2 };
int n = sizeof(array) / sizeof(array[0]);
cout<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
return 0;
}输出
The maximum value of |arr[i] - arr[j]| + |i-j| is 7
更新于: 2020-06-03
264 次查看
广告