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

โจทย์

กำหนด N หาผลรวม |a[i] - a[i+1]| สูงสุดจากทุก permutation ของ {1, 2, ..., N}

ตัวอย่าง: N=4 → Max = 7 (เช่น permutation 2,4,1,3: |2-4|+|4-1|+|3-1| = 2+3+2=7)

วิธีการแก้ปัญหา (สูตรปิด)

สังเกตรูปแบบ: N=2:1, N=3:3, N=4:7, N=5:11, N=6:17, N=7:23, N=8:31

สูตร: maxSum = (N² - 2) / 2

การนำไปสู่สูตร: maxSum = N(N-1)/2 + floor(N/2) - 1 = (N² - 2)/2

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

#include <iostream>
using namespace std;

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

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

ผลลัพธ์

The maximum sum of difference of adjacent elements is 83