home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หาผลรวมความต่างสัมบูรณ์สูงสุดของ Permutation ใดๆ ใน C++

โจทย์

กำหนดอาร์เรย์ หา permutation ที่ให้ผลรวม |a[i] - a[i+1]| (รวม circular |last - first|) สูงสุด

ตัวอย่าง: arr = {9, 1, 6, 3} → Max = 22 (เช่น 9,1,6,3 เรียงใหม่เป็น 3,9,1,6: |3-9|+|9-1|+|1-6|+|6-3| = 6+8+5+3=22)

วิธีการแก้ปัญหา (Greedy)

  1. เรียงอาร์เรย์จากน้อยไปมาก
  2. จัดเรียงใหม่: สลับกันระหว่างค่าน้อยที่สุดและมากที่สุดที่เหลือ → ได้ array แบบ "zigzag": min, max, 2nd min, 2nd max, ...
  3. คำนวณผลรวมความต่างสัมบูรณ์ของ array ใหม่นี้ (รวม circular)

ตัวอย่างโค้ด C++

#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