Tối đa hóa giá trị (arr[i] – i) – (arr[j] – j) trong mảng C++

Đề bài

Cho mảng arr[], tìm max của (arr[i] - i) - (arr[j] - j) với i ≠ j.

Ví dụ: {7,5,10,2,3} → max = (10-2) - (2-3) = 8 - (-1) = 9.

Quan sát quan trọng

Biểu thức = (arr[i] - i) - (arr[j] - j). Để lớn nhất, cần (arr[i] - i) lớn nhất VÀ (arr[j] - j) nhỏ nhất. Chỉ cần tìm max và min của mảng val[k] = arr[k] - k.

Ví dụ minh họa (C++)

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

int getMaxDiff(int* arr, int n) {
    if (n < 2) { cout << "Invalid input\n"; exit(1); }
    int minVal = INT_MAX, maxVal = INT_MIN;
    for (int i = 0; i < n; ++i) {
        int val = arr[i] - i;
        maxVal = max(maxVal, val);
        minVal = min(minVal, val);
    }
    return maxVal - minVal;
}

int main() {
    int arr[] = {7, 5, 10, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Gia tri lon nhat = " << getMaxDiff(arr, n) << endl;
    return 0;
}

Kết quả

Gia tri lon nhat = 9