ในปัญหานี้เราได้รับอาร์เรย์ งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของผลต่างสัมบูรณ์ของการเรียงสับเปลี่ยนใดๆ ใน C++
คำอธิบายปัญหา
เราจะค้นหาการเปลี่ยนแปลงทั้งหมดขององค์ประกอบในอาร์เรย์ที่กำหนด แล้วหาผลรวมของผลต่างสัมบูรณ์ขององค์ประกอบที่อยู่ติดกันของอาร์เรย์ สุดท้ายเราจะคืนจำนวนเงินสูงสุดทั้งหมด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {9, 1, 6, 3} ผลลัพธ์
17
คำอธิบาย
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
.. และการเรียงสับเปลี่ยนทั้งหมดที่มี 6 และ 3 เป็นตัวเลขเริ่มต้น
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ สามารถพบได้โดยค้นหาวิธีที่ดีที่สุดในการเพิ่มโซลูชันให้ได้มากที่สุด และเพื่อให้ได้โซลูชันสูงสุด เราจำเป็นต้องค้นหาความแตกต่างสัมบูรณ์สูงสุดทั้งหมดสำหรับอาร์เรย์ และสิ่งนี้สามารถพบได้โดยใช้ผลต่างสัมบูรณ์ของ |เล็กที่สุด - สูงสุด|.
อัลกอริทึม
ขั้นตอนที่ 1 − เรียงลำดับอาร์เรย์
ขั้นตอนที่ 2 − ตอนนี้ maxsum คำนวณโดยการบวกผลต่างสัมบูรณ์ระหว่างจำนวนที่น้อยที่สุดกับจำนวนที่มากที่สุดของอาร์เรย์ที่เรียงลำดับแล้ว
ขั้นตอนที่ 3 − ในตอนท้าย ให้คืนค่า maxSum
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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);
} ผลลัพธ์
The maximum sum of absolute difference of any permutation is 22
