Tối đa hóa arr[j] - arr[i] + arr[l] - arr[k] với i < j < k < l trong C++

Chúng ta được cho một mảng số nguyên. Mục tiêu là tối đa hóa giá trị biểu thức:

arr[j] - arr[i] + arr[l] - arr[k]; với i < j < k < l là chỉ số phần tử.

Chúng ta sẽ làm bằng cách duyệt tất cả phần tử và tính giá trị biểu thức. Nếu là tối đa tìm thấy cho đến nay thì lưu lại và trả về cuối cùng.

Ví dụ

Đầu vào

arr[] = { 1, 2, 3, 4 }

Đầu ra

Giá trị tối đa cho biểu thức trên: 2

Giải thích − với i < j < k < l, i=0, j=1, k=2, l=3

arr[j] - arr[i] + arr[l] - arr[k] = 2 - 1 + 4 - 3 = 1 + 1 = 2

Đầu vào

arr[] = { 5, 5, 5, 5, 5 }

Đầu ra

Giá trị tối đa cho biểu thức trên: 0

Giải thích − với i < j < k < l, với bất kỳ giá trị i,j,k,l nào

arr[j] - arr[i] + arr[l] - arr[k] = 5 - 5 + 5 - 5 = 0

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên a[] lưu số.
• Hàm maximizeSum(int arr[], int n) nhận mảng và độ dài n, trả về giá trị tối đa của arr[j] - arr[i] + arr[l] - arr[k] với i < j < k < l.
• Biến sum lưu tổng của arr[j] - arr[i] và arr[l] - arr[k].
• Khởi tạo maxx = arr[0] làm tổng tối đa ban đầu.
• Duyệt mảng từ i=0, j=1, k=2, l=3 đến i < n-3, j < n-2, k < n-1 và l < n.
• Với mỗi chỉ số i,j,k,l tính arr[j] - arr[i] + arr[l] - arr[k] và lưu vào sum.
• Nếu sum hiện tại >= maxx thì cập nhật maxx.
• Cuối cùng trả về maxx là kết quả mong muốn.

Ví dụ mã nguồn

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

// Hàm tối đa hóa tổng các số được chọn
int maximizeSum(int arr[], int n) { 
    int sum = 0; 
    int maxx = arr[0]; 
    for (int i = 0; i < n - 3; i++) 
        for (int j = i + 1; j < n - 2; j++) 
            for (int k = j + 1; k < n - 1; k++) 
                for (int l = k + 1; l < n; l++) { 
                    sum = arr[j] - arr[i] + arr[l] - arr[k]; 
                    if (sum >= maxx) 
                        maxx = sum; 
                } 
    return maxx; 
} 

int main() { 
    int a[] = {5, 3, 9, 2, 20}; 
    int n = sizeof(a) / sizeof(a[0]); 
    cout << "Giá trị tối đa hóa: " << maximizeSum(a, n); 
    return 0; 
}

Kết quả

Giá trị tối đa hóa: 24