ค่าสูงสุดของ |arr[0]-arr[1]| + |arr[1]-arr[2]| + ... + |arr[n-2]-arr[n-1]| เมื่อองค์ประกอบมาจาก 1 ถึง n ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม n ตัวในช่วง [1,n] งานของเราคือสร้างโปรแกรมที่จะหาค่าสูงสุดของ |arr[0] - arr[1]| + |arr[1] - arr[2]| + ... + |arr[n-2] - arr[n-1]|

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - array= {1, 2, 3}

เอาต์พุต - 3

คำอธิบาย -

max sum is |1-3|+|2-1| = 3

ในการแก้ปัญหานี้ วิธีง่ายคือสร้างการเรียงสับเปลี่ยนทั้งหมดจากอาร์เรย์ และหาค่าสูงสุดของค่าทั้งหมดจากการเรียงสับเปลี่ยน วิธีที่มีประสิทธิภาพมากกว่าคือการสรุปค่าสูงสุดสำหรับแต่ละค่า n แล้วสร้างสูตรทั่วไป

ดังนั้น:

Maximum sum for (n = 1) = 0
Maximum sum for (n = 2) = 1
Maximum sum for (n = 3) = 3
Maximum sum for (n = 4) = 7
Maximum sum for (n = 5) = 11
ดังนั้น ค่าสูงสุดคือ 0, 1, 3, 7, 11...

สูตรทั่วไปคือ ((n*n/2)-1)

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

โปรแกรมแสดงการทำงานของวิธีแก้ปัญหาของเรา:

#include <iostream>
using namespace std;

int maxAbsVal(int n) {
    if (n == 1)
        return 0;
    return ((n*n/2) - 1);
}

int main() {
    int n = 4;
    cout<<"The maximum sum of absolute difference is "<<maxAbsVal(n);
    return 0;
}

ผลลัพธ์

The maximum sum of absolute difference is 7