資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告