Trong bài toán này, chúng ta được cung cấp một mảng. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Tổng số chênh lệch tuyệt đối lớn nhất của bất kỳ hoán vị nào trong C ++.
Mô tả vấn đề
Chúng ta sẽ tìm tất cả các hoán vị của các phần tử của mảng đã cho. Và sau đó tìm tổng của hiệu số tuyệt đối của các phần tử liền kề của mảng. Cuối cùng, chúng tôi sẽ trả lại số tiền tối đa.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {9, 1, 6, 3} Đầu ra
17
Giải thích
All permutations of the array with sum of absolute difference of adjacent elements.
{9, 1, 6, 3},
sum= |9-1| + |1-6| + |6-3| + |3-9| = 8+5+3+6 = 16
{9, 1, 3, 6},
sum= |9-1| + |1-3| + |3-6| + |6- 9| = 8+2+3+3 = 16
{9, 6, 1, 3},
sum= |9-6| + |6-1| + |1-3| + |3 - 9| = 3+5+2+6 = 16
{9, 6, 3, 1},
sum= |9-6| + |6-3| + |3-1| + |1 - 9| = 3+3+2+8 = 16
{9, 3, 1, 6},
sum= |9-3| + |3-1| + |1-6| + |6- 9| = 6+2+5+3 = 16
{9, 3, 6, 1},
sum= |9-3| + |3-6| + |6-1| + |1- 9| = 6+3+5+8 = 22
{1, 9, 6, 3},
sum= |1-9| + |9-6| + |6-3| + |3-1| = 8+3+3+2 = 16
{1, 9, 3, 6},
sum= |1-9| + |9-3| + |3-6| +
|6 - 1| = 8+6+3+5 = 22
{1, 6, 9, 3},
sum= |1-6| + |6-9| + |9-3| + |3 - 1| = 5+3+6+2 = 16
{1, 6, 3, 9},
sum= |1-6| + |6-3| + |3-9| + |9-1| = 5+3+6+8 = 22
{1, 3, 9, 6},
sum= |1-3| + |3-9| + |9-6| + |6-1| = 2+6+3+5 = 16
{1, 3, 6, 9},
sum= |1-3| + |3-6| + |6-9| + |9 - 1| = 2+3+3+8 = 16
.. Và tất cả các hoán vị lấy 6 và 3 đều là số bắt đầu.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề có thể được tìm thấy bằng cách tìm ra cách tốt nhất để tối đa hóa giải pháp. Và để tối đa hóa giải pháp, chúng ta cần tìm tất cả các khác biệt tuyệt đối lớn nhất cho mảng. Và điều này có thể được tìm thấy bằng cách sử dụng sự khác biệt tuyệt đối của | nhỏ nhất - cao nhất |.
Thuật toán
Bước 1 - Sắp xếp mảng.
Bước 2 - Bây giờ, giá trị lớn nhất được tính bằng cách cộng hiệu số tuyệt đối giữa số nhỏ nhất và số lớn nhất của mảng đã sắp xếp.
Bước 3 - Cuối cùng, trả về maxSum.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <bits/stdc++.h>
using namespace std;
int calcMaxSumAbsDiff(int arr[], int N){
int maxSumArray[N];
int j = 0, maxSum = 0;
sort(arr, arr + N);
for (int i = 0; i < (N/2); ++i){
maxSumArray[j] = arr[i];
maxSumArray[j+1] = arr[N - i - 1];
j += 2;
}
if (N % 2 != 0)
maxSumArray[j] = arr[N/2];
for (int i = 0; i < N - 1; i++){
maxSum += abs(maxSumArray[i] - maxSumArray[i + 1]);
}
maxSum += abs(maxSumArray[N - 1] - maxSumArray[0]);
return maxSum;
}
int main(){
int arr[] = {9, 1, 6, 3};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum of absolute difference of any permutation is "<<calcMaxSumAbsDiff(arr, N);
} Đầu ra
The maximum sum of absolute difference of any permutation is 22