最长递增子序列的构造(N log N)


难度级别
经常问 亚马逊 银行集市 Paytm Samsung
排列 二进制搜索 动态编程

问题陈述

给你一个 排列 of 整数。 问题“最长增长子序列的构造(N log N)”要求构造最长增长子序列。

使用案列

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

说明

我们找出在数组中增加的最长子序列。

最长递增子序列的构造(N log N)

最长递增子序列(N log N)的构造算法

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

说明

我们给出了一个整数数组,并要求构造 最长的递增子序列。 为此,我们将使用两个数组lastIndexes和firstIndexes并将其分别填充为0和-1的值。 firstIndexes数组将初始化为1。因为这会将值存储为位置作为索引。 我们将在遍历数组时更新值。

我们将遍历数组从1到n。 其中n是数组的长度。 在遍历时,数组lastIndexes将用作数组的位置或索引。 我们将检查一些条件,我们将检查当前数组元素是否小于lastIndexes [leng-1]的数组。 最初将length定义为1,这意味着至少我们将拥有length 1的子序列。因此,如果上述条件为true,则将lastIndexes [0]更新为1。

我们需要检查arr [i]是否大于lastIndexes [n-1]的数组。 然后更新两个数组,将firstIndexes [i]设置为lastIndexes [n-1]的最后一个值,将lastIndexes [leng]设置为i,并增加leng值。 否则,我们必须找出当前数组元素的位置。 为此,我们将使用二进制搜索并将该索引获取到该位置。 并将lastIndexes [position-1]的值更新为firstIndexes [i],将lastIndexes [position]的值更新为i。

遍历后,我们需要打印数组。 为此,我们将从最后一个遍历到0th 每次遍历后定位并初始化每个索引为firstIndexes [i],并打印数组的每个可能值。

代码

构造最长递增子序列的C ++代码(N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

构造最长递增子序列的Java代码(N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

复杂度分析

时间复杂度

O(n log n) 其中“ n”是数组中元素的数量。 由于我们使用了二分查找法,该算法为我们提供了一个对数因子。 但是,如果我们不得不为每个索引调用二进制搜索。 然后,在最坏的情况下,时间复杂度将为O(N log N)。

空间复杂度

O(N) 其中“ n”是数组中元素的数量。 由于我们创建了两个临时数组firstIndexes和lastIndexes。 空间复杂度变为 上).