# 最大长度子序列，相邻元素之间的差为0或1

## 使用案列

`arr[] = {1, 4, 5, 2, 6, 5, 4, 8}`
`5`

`arr[] = {1, -3, -2, 0, -1, -2, -3, -4}`
`6`

## 查找相邻元素之间的差异为0或1的最大长度子序列的算法

```1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
1. Initialize a variable temp to 0.
2. Check if Map contains the key as arr[i-1],
1. If true, then get the value of arr[i-1] and store it to temp.
3. Check if Map contains the key as arr[i],
1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
4. Check if Map contains the key as arr[i+1],
1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
5. Check if the temp is greater than maxValue,
1. If true then store the value of temp to maxValue.
6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.```

Arr [] = {1，4，5，2，6，5，4，8，XNUMX}

i = 0，arr [i] = 1，temp = 0，maxValue = 0 Map = {}

i = 1，arr [i] = 4，temp = 0，maxValue = 1。

i = 2，arr [i] = 5，temp = 0，maxValue = 1。

## 代码

### C ++代码查找最大长度子序列，相邻元素之间的差为0或1

```#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
unordered_map<int, int> MAP;
int maxValue = 0;
for (int i=0; i<n; i++)
{
int temp = 0;
if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
temp = MAP[arr[i]-1];

if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
temp = MAP[arr[i]];

if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
temp = MAP[arr[i]+1];

MAP[arr[i]] = temp + 1;

if (maxValue < MAP[arr[i]])
maxValue = MAP[arr[i]];
}
return maxValue;
}
int main()
{
int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout << getMaximumLenSubsequence(arr, n);
return 0;
}
```
`5`

### Java代码查找最大长度子序列，相邻元素之间的差为0或1

```import java.util.HashMap;

class subsequenceLength
{
public static int getMaximumLenSubsequence(int[] arr)
{
int maxValue = 0;
HashMap<Integer, Integer> MAP = new HashMap<>();
for (int i = 0; i < arr.length; i++)
{
int temp = 0;
if (MAP.containsKey(arr[i] - 1))
{
temp = MAP.get(arr[i] - 1);
}

if (MAP.containsKey(arr[i]))
{
temp = Math.max(temp, MAP.get(arr[i]));
}

if (MAP.containsKey(arr[i] + 1))
{
temp = Math.max(temp, MAP.get(arr[i] + 1));
}
temp++;
if (temp > maxValue)
{
maxValue = temp;
}
MAP.put(arr[i], temp);
}
return maxValue;
}
public static void main(String[] args)
{
int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
System.out.println(getMaximumLenSubsequence(arr));
}
}
```
`5`

## 复杂度分析

### 时间复杂度

O（N） 哪里 “ n” 是数组中元素的数量。 我们仅遍历了数组中的所有元素。 因为我们使用了HashMap，所以我们能够以线性时间复杂度来做到这一点。

### 空间复杂度

O（N） 哪里 “ n” 是数组中元素的数量。 由于我们在地图中存储与元素相关的数据，因此空间复杂度也是线性的。