数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 将数组转为严格递增整数数组，且更改最小
在本教程中，我们将讨论一个程序，该程序将数组转为严格递增整数数组，且更改最小。
为此，我们将提供一个数组。我们的任务是通过最少数量的元素更改使数组中的元素按严格递增顺序排列。
范例
#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;
}输出
2
更新时间:2020 年 1 月 29 日
139 次浏览
广告