Chuyển đổi thành Mảng số nguyên tăng nghiêm ngặt với các thay đổi tối thiểu trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi thành mảng số nguyên tăng dần với các thay đổi tối thiểu.

Đối với điều này, chúng tôi sẽ được cung cấp một mảng. Nhiệm vụ của chúng ta là thay đổi các phần tử của mảng theo thứ tự tăng dần theo số lượng thay đổi tối thiểu trong các phần tử.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//calculating number of changes required
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]);
   }
   //returning the changes required
   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;
}

Đầu ra

2