dsal 最长严格双子序列的长度

最长严格双子序列的长度

原文：https://www.geeksforgeeks.org/length-longest-strict-bitonic-subsequence/

给定一个包含n个整数的数组arr[]。问题是找到最长的严格双音子序列的长度。如果子序列先增大然后减小，且条件是在递增和递减部分中相邻项之间的绝对差仅为 1，则该子序列称为严格双子序列。按升序排序的序列被视为双子序列，而降序部分为空。类似地，降序序列被视为双子序列，而升序部分为空。

示例：

Input : arr[] = {1, 5, 2, 3, 4, 5, 3, 2}
Output : 6
The Longest Strict Bitonic Subsequence is:
{1, 2, 3, 4, 3, 2}.

Input : arr[] = {1, 2, 5, 3, 6, 7, 4, 6, 5}
Output : 5

方法 1：可以使用找到最长双子序列的概念来解决该问题。唯一需要保持的条件是，相邻项之间的差应仅为 1。它的时间复杂度为O(N ^ 2)。

方法 2（有效方法）：想法是创建两个哈希映射inc和dcr，其元组的格式为(ele, len)，其中len表示映射inc中以元素ele结尾的最长递增子序列的长度，以及映射dcr中以ele开头的最长递减子序列的长度。还创建两个数组len_inc[]和len_dcr[]，其中len_inc[i]代表以元素arr[i]结尾的最大递增子序列的长度，和len_dcr[i]表示从元素arr[i]开始的最大递减子序列的长度。现在，对于哈希表inc中存在的每个元素arr[i]，我们可以找到值arr[i] - 1的长度。令该值为v（最初v将为 0）。现在，以arr[i]结尾的最长递增子序列的长度将为v + 1。在哈希表inc和数组len_inc[]中的元素arr[i]的相应索引i处更新此长度。现在，从右向左遍历数组，我们可以类似地填充哈希表dcr和数组len_dcr[]，以得到最长的递减子序列。最后，对于每个元素arr[i]，我们计算len_inc[i] + len_dcr[i] – 1并返回最大值。

注意：在这里，增加和减少子序列仅表示相邻元素之间的差仅为 1。

C++

// C++ implementation to find length of longest  
// strict bitonic subsequence  
#include <bits/stdc++.h> 
using namespace std; 

// function to find length of longest  
// strict bitonic subsequence  
int longLenStrictBitonicSub(int arr[], int n) 
{ 
    // hash table to map the array element with the 
    // length of the longest subsequence of which 
    // it is a part of and is the last/first element of 
    // that subsequence 
    unordered_map<int, int> inc, dcr; 

    // arrays to store the length of increasing and 
    // decreasing subsequences which end at them 
    // or start from them   
    int len_inc[n], len_dcr[n]; 

    // to store the length of longest strict  
    // bitonic subsequence 
    int longLen = 0; 

    // traverse the array elements 
    // from left to right 
    for (int i=0; i<n; i++) 
    { 
        // initialize current length  
        // for element arr[i] as 0 
        int len = 0; 

        // if 'arr[i]-1' is in 'inc' 
        if (inc.find(arr[i]-1) != inc.end()) 
            len = inc[arr[i]-1]; 

        // update arr[i] subsequence length in 'inc'     
        // and in len_inc[] 
        inc[arr[i]] = len_inc[i] = len + 1;  
    } 

    // traverse the array elements 
    // from right to left 
    for (int i=n-1; i>=0; i--) 
    { 
        // initialize current length  
        // for element arr[i] as 0 
        int len = 0; 

        // if 'arr[i]-1' is in 'dcr'  
        if (dcr.find(arr[i]-1) != dcr.end()) 
            len = dcr[arr[i]-1]; 

        // update arr[i] subsequence length in 'dcr' 
        // and in len_dcr[]     
        dcr[arr[i]] = len_dcr[i] = len + 1;  
    } 

    // calculating the length of all the strict  
    // bitonic subsequence 
    for (int i=0; i<n; i++) 
        if (longLen < (len_inc[i] + len_dcr[i] - 1)) 
            longLen = len_inc[i] + len_dcr[i] - 1; 

    // required longest length strict  
    // bitonic subsequence 
    return longLen;         
} 

// Driver program to test above 
int main() 
{ 
    int arr[] = {1, 5, 2, 3, 4, 5, 3, 2}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Longest length strict bitonic subsequence = "
         << longLenStrictBitonicSub(arr, n); 
    return 0; 
}

Java

// Java implementation to find length of longest  
// strict bitonic subsequence  
import java.util.*; 

class GfG  
{ 

// function to find length of longest  
// strict bitonic subsequence  
static int longLenStrictBitonicSub(int arr[], int n)  
{  
    // hash table to map the array element with the  
    // length of the longest subsequence of which  
    // it is a part of and is the last/first element of  
    // that subsequence  
    HashMap<Integer, Integer> inc = new HashMap<Integer, Integer> (); 
    HashMap<Integer, Integer> dcr = new HashMap<Integer, Integer> ();  

    // arrays to store the length of increasing and  
    // decreasing subsequences which end at them  
    // or start from them  
    int len_inc[] = new int[n]; 
    int len_dcr[] = new int[n];  

    // to store the length of longest strict  
    // bitonic subsequence  
    int longLen = 0;  

    // traverse the array elements  
    // from left to right  
    for (int i = 0; i < n; i++)  
    {  
        // initialize current length  
        // for element arr[i] as 0  
        int len = 0;  

        // if 'arr[i]-1' is in 'inc'  
        if (inc.containsKey(arr[i] - 1))  
            len = inc.get(arr[i] - 1);  

        // update arr[i] subsequence length in 'inc'      
        // and in len_inc[]  
        len_inc[i] = len + 1; 
        inc.put(arr[i], len_inc[i]); 
    }  

    // traverse the array elements  
    // from right to left  
    for (int i = n - 1; i >= 0; i--)  
    {  
        // initialize current length  
        // for element arr[i] as 0  
        int len = 0;  

        // if 'arr[i]-1' is in 'dcr'  
        if (dcr.containsKey(arr[i] - 1))  
            len = dcr.get(arr[i] - 1);  

        // update arr[i] subsequence length in 'dcr'  
        // and in len_dcr[]  
        len_dcr[i] = len + 1; 
        dcr.put(arr[i], len_dcr[i]);  
    }  

    // calculating the length of all the strict  
    // bitonic subsequence  
    for (int i = 0; i < n; i++)  
        if (longLen < (len_inc[i] + len_dcr[i] - 1))  
            longLen = len_inc[i] + len_dcr[i] - 1;  

    // required longest length strict  
    // bitonic subsequence  
    return longLen;      
}  

// Driver code  
public static void main(String[] args)  
{  
    int arr[] = {1, 5, 2, 3, 4, 5, 3, 2};  
    int n = arr.length;  
    System.out.println("Longest length strict " +  
                            "bitonic subsequence = " +  
                            longLenStrictBitonicSub(arr, n));  
} 
}  

// This code is contributed by  
// prerna saini

Python3

# Python3 implementation to find length of  
# longest strict bitonic subsequence 

# function to find length of longest 
# strict bitonic subsequence 
def longLenStrictBitonicSub(arr, n): 

    # hash table to map the array element  
    # with the length of the longest subsequence  
    # of which it is a part of and is the  
    # last/first element of that subsequence 
    inc, dcr = dict(), dict() 

    # arrays to store the length of increasing 
    # and decreasing subsequences which end at  
    # them or start from them 
    len_inc, len_dcr = [0] * n, [0] * n 

    # to store the length of longest strict 
    # bitonic subsequence 
    longLen = 0

    # traverse the array elements 
    # from left to right 
    for i in range(n): 

        # initialize current length 
        # for element arr[i] as 0 
        len = 0

        # if 'arr[i]-1' is in 'inc' 
        if inc.get(arr[i] - 1) in inc.values(): 
            len = inc.get(arr[i] - 1) 

        # update arr[i] subsequence length in 'inc'      
        # and in len_inc[]  
        inc[arr[i]] = len_inc[i] = len + 1

    # traverse the array elements 
    # from right to left 
    for i in range(n - 1, -1, -1): 

        # initialize current length 
        # for element arr[i] as 0 
        len = 0

        # if 'arr[i]-1' is in 'dcr' 
        if dcr.get(arr[i] - 1) in dcr.values(): 
            len = dcr.get(arr[i] - 1) 

        # update arr[i] subsequence length   
        # in 'dcr' and in len_dcr[]  
        dcr[arr[i]] = len_dcr[i] = len + 1

    # calculating the length of  
    # all the strict bitonic subsequence  
    for i in range(n): 
        if longLen < (len_inc[i] + len_dcr[i] - 1): 
            longLen = len_inc[i] + len_dcr[i] - 1

    # required longest length strict  
    # bitonic subsequence  
    return longLen 

# Driver Code 
if __name__ == "__main__": 
    arr = [1, 5, 2, 3, 4, 5, 3, 2] 
    n = len(arr) 
    print("Longest length strict bitonic subsequence =", 
           longLenStrictBitonicSub(arr, n)) 

# This code is contributed by sanjeev2552

C

// C# implementation to find length of longest  
// strict bitonic subsequence  
using System; 
using System.Collections.Generic; 

class GfG  
{  

    // function to find length of longest  
    // strict bitonic subsequence  
    static int longLenStrictBitonicSub(int []arr, int n)  
    {  
        // hash table to map the array  
        // element with the length of  
        // the longest subsequence of  
        // which it is a part of and  
        // is the last/first element of  
        // that subsequence  
        Dictionary<int, int> inc = new Dictionary<int, int> ();  
        Dictionary<int, int> dcr = new Dictionary<int, int> ();  

        // arrays to store the length  
        // of increasing and decreasing  
        // subsequences which end at them  
        // or start from them  
        int []len_inc = new int[n];  
        int []len_dcr = new int[n];  

        // to store the length of longest strict  
        // bitonic subsequence  
        int longLen = 0;  

        // traverse the array elements  
        // from left to right  
        for (int i = 0; i < n; i++)  
        {  
            // initialize current length  
            // for element arr[i] as 0  
            int len = 0;  

            // if 'arr[i]-1' is in 'inc'  
            if (inc.ContainsKey(arr[i] - 1))  
                len = inc[arr[i] - 1];  

            // update arr[i] subsequence length       
            // in 'inc' and in len_inc[]  
            len_inc[i] = len + 1;  
            if (inc.ContainsKey(arr[i])) 
            { 
                inc.Remove(arr[i]); 
                inc.Add(arr[i], len_inc[i]);  
            } 
            else
                inc.Add(arr[i], len_inc[i]); 
        }  

        // traverse the array elements  
        // from right to left  
        for (int i = n - 1; i >= 0; i--)  
        {  
            // initialize current length  
            // for element arr[i] as 0  
            int len = 0;  

            // if 'arr[i]-1' is in 'dcr'  
            if (dcr.ContainsKey(arr[i] - 1))  
                len = dcr[arr[i] - 1];  

            // update arr[i] subsequence length in 'dcr'  
            // and in len_dcr[]  
            len_dcr[i] = len + 1;  
            if (dcr.ContainsKey(arr[i])) 
            { 
                dcr.Remove(arr[i]); 
                dcr.Add(arr[i], len_dcr[i]);  
            } 
            else
                dcr.Add(arr[i], len_dcr[i]);  
        }  

        // calculating the length of all the strict  
        // bitonic subsequence  
        for (int i = 0; i < n; i++)  
            if (longLen < (len_inc[i] + len_dcr[i] - 1))  
                longLen = len_inc[i] + len_dcr[i] - 1;  

        // required longest length strict  
        // bitonic subsequence  
        return longLen;  
    }  

    // Driver code  
    public static void Main(String[] args)  
    {  
        int []arr = {1, 5, 2, 3, 4, 5, 3, 2};  
        int n = arr.Length;  
        Console.WriteLine("Longest length strict " +  
                            "bitonic subsequence = " +  
                            longLenStrictBitonicSub(arr, n));  
    }  
}  

// This code is contributed by Rajput-Ji

输出：

Longest length strict bitonic subsequence = 6

时间复杂度：O(n)。

辅助空间：O(n)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/36384.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

分类

最近更新

dsal 最长严格双子序列的长度

最长严格双子序列的长度

C++

Java

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

dsal 最长严格双子序列的长度

最长严格双子序列的长度

C++

Java

Python3

C

留言

联系客服

dsal 查看更多书籍