資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學相鄰元素差為 0 或 1 的最大長度子序列 | C++ 中的集合 2
給定一個任意大小的陣列，任務是找到該陣列中的子序列，其元素相鄰元素之間的差為 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。
下面程式中使用的方法如下
輸入一個整數型別的陣列，其中可以包含正數和負數。
計算陣列的大小，並將陣列和大小傳遞給函式以進行進一步的功能。
取一個臨時變數 maximum 並將其設定為 0，再取另一個臨時變數 i 並將其設定為 0。
建立一個 unordered_map 型別的變數 un_map。
啟動迴圈，直到 i 小於 size。
在迴圈內部，將 len 設定為 0，並檢查是否 un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]，如果是，則將 len 設定為 len = un_map[arr[i]-1]。
檢查是否 un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]，如果是，則將 len 設定為 len = un_map[arr[i]]。
檢查是否 un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]，如果是，則將 len 設定為 len = un_map[arr[i]+1]。
現在設定 un_map[arr[i]] = len + 1。
檢查 maximum 是否小於 un_map[arr[i]]，如果是，則將 maximum 設定為 un_map[arr[i]]。
遞增 i 的值。
返回 maximum。
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
//calculate the maximum subsequence
int maximum_adj(int arr[], int size){
int maximum = 0, i = 0;
unordered_map<int, int> un_map;
while(i < size){
int len = 0;
if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
len = un_map[arr[i]-1];
}
if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
len = un_map[arr[i]];
}
if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
len = un_map[arr[i]+1];
}
un_map[arr[i]] = len + 1;
if (maximum < un_map[arr[i]]){
maximum = un_map[arr[i]];
}
i++;
}
return maximum;
}
int main(){
int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum length subsequence with difference between adjacent elements as either 0
or 1 are: "<< maximum_adj(arr, size);
return 0;
}輸出
Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4
119 次瀏覽
