Giá trị lớn nhất của |arr[0] – arr[1]| + |arr[1] – arr[2]| + … + |arr[n-2] – arr[n-1]| khi các phần tử từ 1 đến n trong C++

Trong bài toán này, chúng ta được cho một mảng n số nguyên trong phạm vi [1,n]. Nhiệm vụ là tạo một chương trình tìm giá trị lớn nhất của |arr[0] – arr[1]| + |arr[1] – arr[2]| + … + |arr[n-2] – arr[n-1].

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào – mảng= {1, 2, 3}

Đầu ra – 3

Giải thích –

tổng lớn nhất là |1-3|+|2-1| = 3

Để giải quyết bài toán này, một cách tiếp cận đơn giản là tạo tất cả các hoán vị từ mảng. Và tìm giá trị lớn nhất của tất cả các giá trị từ hoán vị. Một phương pháp hiệu quả hơn là khái quát hóa tất cả các giá trị lớn nhất cho mỗi giá trị của n và sau đó tạo một công thức chung.

Vì vậy,

Tổng lớn nhất cho (n = 1) = 0
Tổng lớn nhất cho (n = 2) = 1
Tổng lớn nhất cho (n = 3) = 3
Tổng lớn nhất cho (n = 4) = 7
Tổng lớn nhất cho (n = 5) = 11
Vì vậy, giá trị lớn nhất là 0, 1, 3, 7, 11…

Công thức chung là, ((n*n/2)-1)

Ví dụ

Chương trình minh họa hoạt động của giải pháp:

#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<<"Tổng lớn nhất của hiệu tuyệt đối là "<<maxAbsVal(n);
    return 0;
}

Kết quả

Tổng lớn nhất của hiệu tuyệt đối là 7