Chuyển mảng thành mảng tăng chặt với ít thay đổi nhất trong C++

Cho một mảng, thay đổi các phần tử để mảng trở thành tăng chặt (strictly increasing) với số lần thay đổi tối thiểu.

Ví dụ

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

int remove_min(int arr[], int n) {
    int LIS[n], len = 0;
    for (int i = 0; i < n; i++) LIS[i] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && (i-j) <= (arr[i]-arr[j])) {
                LIS[i] = max(LIS[i], LIS[j] + 1);
            }
        }
        len = max(len, LIS[i]);
    }
    return n - len;
}

int main() {
    int arr[] = {1, 2, 6, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << remove_min(arr, n);
    return 0;
}

Kết quả

2