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


难度级别 中等
经常问 思科 Expedia的 Qualtrics SAP实验室 Teradata数据
排列 动态编程

问题陈述

给你一个 整数 排列。 问题“相邻元素之间的差异为0或1的最大长度子序列”要求找出相邻元素之间的差异为0或1的最大子序列长度。

使用案列

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

说明

子序列= 4,5,6,5,4

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

说明

子序列= -3,-2,-1,-2,-3,-4

查找相邻元素之间的差异为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.

说明

我们得到了一个 整数 数组,问题陈述要求找出最大子序列长度。 并且选择的子序列应使其相邻值之间的差值应为0或1。为解决此问题,我们将使用 散列 使我们的解决方案高效。 我们将把键作为数组的元素,并获取键的值始终找到最大值并将其存储到temp。

让我们考虑一个示例并理解这一点:

使用案列

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

我们要做的第一件事是声明一个 地图 因为我们将根据我们讨论的算法存储数组元素和值temp。 将maxValue的值设置为0。我们将返回此变量。 该变量中的内容将是我们的答案。 我们将遍历数组并使其达到数组的长度。 每次我们使用新值i遍历数组时,都会将temp值初始化为0。

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

检查要满足的条件。 在这种情况下,没有条件。 因此它执行temp ++并检查temp是否大于maxValue。 如果为true,则将temp存储到maxValue中,然后将值和temp插入到映射中。

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

地图= {1,1}

与上述条件相同,我们只是将值插入到map中

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

地图= {1:1,4:1}

这次我们找到映射包含arr [i] -1为4的第一个条件更正。因此,将1作为临时文件并执行temp ++。 然后将maxValue更改为2并在其中插入arr [i]和temp。

就像这样,我们将继续检查条件并获取临时值。 继续将其插入到地图中,最后,我们获得maxValue中的值作为输出。

最大长度子序列,相邻元素之间的差为0或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” 是数组中元素的数量。 由于我们在地图中存储与元素相关的数据,因此空间复杂度也是线性的。