Tổng chênh lệch tuyệt đối giữa các phần tử liền kề lớn nhất trong hoán vị (C++)

Cho N, tìm hoán vị của 1..N cho tổng |a[i]-a[i+1]| lớn nhất.

Ví dụ: N=4 → max = 7 (hoán vị {2,4,1,3} hoặc {3,1,4,2}).

Công thức toán học

Quan sát chuỗi maxSum: N=2→1, 3→3, 4→7, 5→11, 6→17, 7→23, 8→31. Suy ra công thức: maxSum = (N² - 2) / 2.

Ví dụ (C++)

#include <iostream>
using namespace std;

int calcMaxSumofDiff(int N){
    return ((N*N) - 2) / 2;
}

int main(){
    int N=13;
    cout<<"The maximum sum of difference of adjacent elements is "<<calcMaxSumofDiff(N);
    return 0;
}

Đầu ra

The maximum sum of difference of adjacent elements is 83