資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告