数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中查找相邻元素差值为 0 或 1 的最大长度子序列
给定一个任意大小的数组，任务是找到该数组中的子序列，其中元素的相邻元素之间的差值为 0 或 1。
输入 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}
输出 − 相邻元素差值为 0 或 1 的最大长度子序列为 − 3
说明 − 数组中相邻元素的子序列，其差值为 0 或 1 为 {2, 1}。因此，子序列的最大长度为 2。
输入 − int arr[] = { 2, 1, 7, 6, 5}
输出 − 相邻元素差值为 0 或 1 的最大长度子序列为 − 3
说明 − 数组中相邻元素的差值为 0 或 1 为 {7, 6, 5}。因此，子序列的最大长度为 3。
下面程序中使用的方案如下
- 输入一个整数类型的数组，该数组可以包含正数和负数。
- 计算数组的大小，并将数组和大小传递给函数以进行进一步的功能。
- 使用与输入数组相同大小的临时数组，例如 temp[size]，以及另一个变量 maximum 并将其设置为 0。
- 从 0 到数组大小开始循环
- 在循环内，将 temp[i] 设置为 1
- 开始另一个循环，从 1 到大小
- 在循环内，开始另一个循环 j 从 0 到 j 小于 i
- 在循环内，检查相邻元素的差值是否为 0 或 1，如果是，则将 temp[i] 设置为 temp[i] + 1
- 从 0 到大小开始循环
- 在循环内，检查 maximum 是否小于 temp[i]，如果是，则将 maximum 设置为 temp[i]
- 返回 maximum
- 打印结果
示例
#include <bits/stdc++.h>
using namespace std;
//function to calculate the maximum difference
int maximum_adja(int arr[], int size){
int temp[size], maximum = 0;
for (int i=0; i<size; i++){
temp[i] = 1;
}
for (int i=1; i<size; i++){
for (int j=0; j<i; j++){
if (abs(arr[i] - arr[j]) <= 1 && temp[i] < temp[j] + 1){
temp[i] = temp[j] + 1;
}
}
}
for (int i=0; i<size; i++){
if (maximum < temp[i]){
maximum = temp[i];
}
}
return maximum;
}
int main(){
int arr[] = {1, 5, 3, 7, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum length subsequence with difference between adjacent elements as either 0
or 1 is: "<<maximum_adja(arr, size);
return 0;
}输出
Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3
更新于: 2020年8月3日
772 次查看
广告