Tổng chênh lệch tuyệt đối lớn nhất của hoán vị mảng trong C++

Cho mảng, tìm hoán vị cho tổng |a[i]-a[i+1]| (tính cả vòng tròn |last-first|) lớn nhất.

Ví dụ: arr=[9,1,6,3] → max = 22 (hoán vị {9,3,6,1} hoặc {1,9,3,6}...).

Giải thuật Tham lam

1. Sắp xếp mảng tăng dần.
2. Xếp lại mảng mới: xen kẽ phần tử nhỏ nhất và lớn nhất còn lại (small, large, 2nd small, 2nd large, ...).
3. Tính tổng chênh lệch tuyệt đối giữa các phần tử liền kề (kể cả first-last).

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

int calcMaxSumAbsDiff(int arr[], int N){
    int maxSumArray[N], j=0, maxSum=0;
    sort(arr, arr+N);
    for(int i=0;i<N/2;i++){
        maxSumArray[j++]=arr[i];
        maxSumArray[j++]=arr[N-i-1];
    }
    if(N%2) 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... is "<<calcMaxSumAbsDiff(arr,N);
}

Đầu ra

The maximum sum of absolute difference of any permutation is 22