Максимальная длина увеличения супермассива, полученного путем объединения двух увеличивающихся подмассивов

Question

Проблема: Для данного массива найдите два увеличивающихся подмассива (скажем, a и b), чтобы при объединении они создавали один увеличивающийся массив (скажем, ab). Нам нужно найти максимально возможную длину массива ab.

Например: дано array = [2 3 1 2 5 4 5]

Два подмассива: a = [2 3], b = [4, 5] и ab = [2 3 4 5] Вывод: length(ab) = 4

Answer 1

Я бы решил, используя грубую силу. Грубой силой я могу получить все подмассивы и затем проверить, увеличивается ли он. Затем я могу использовать массив слияния и проверить, есть ли перекрывающиеся элементы. Если есть перекрывающиеся элементы, удалите их и сохраните длину.

Сложность времени для получения всех подмассивов будет O(n^2) (я предполагаю, что подмассив будет поддерживать относительный порядок, а вы не имеете в виду все подмножества). А затем отсортирует подмассивы с использованием очереди, и стратегия сортировки будет соответствовать первому элементу. Затем я проверю, сколько можно объединить с увеличивающимся свойством (что вы используете для объединения уже отсортированного массива).

Затем подсчитайте строго увеличивающиеся массивы после объединения.

Два других подхода могут использоваться динамическим c программированием (это то же самое, что и самый длинный непрерывный увеличивающийся подрешетку): ( Смотрите здесь )

Первый подход:

 public int lengthOfLIS(int[] nums) {            
    if(nums.length == 0) { return 0; }

    int[] dp = new int[nums.length];

    int len = 0;

    for(int n: nums) {

        // Find the position of it in binary tree.
        int pos = Arrays.binarySearch(dp, 0, len, n);

        // Convert the negative position to positive.
        if(pos < 0) { pos = -1*(pos + 1); }

        // assign the value to n
        dp[pos] = n;

        // If the length of the dp grows and becomes equal to the current len
        // assign the output length to that.
        if(pos == len) {
           len++;
        }
    }

    // Return the length.
    return len;
}

Другой метод:

public int lengthOfLIS(int[] nums) {

    if(nums == null || nums.length == 0) { return 0; }
    int n = nums.length;

    Integer lis[] = new Integer[n]; 
    int max = 0; 

    /* Initialize LIS values for all indexes 
    for ( int i = 0; i < n; i++ ) {
        lis[i] = 1; 
    }

    /* Compute optimized LIS values in bottom up manner 
    for (int i = 1; i < n; i++ ) {
        for ( int j = 0; j < i; j++ )  {
            if ( nums[i] > nums[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1; 
            }
        } 
    }
    max = Collections.max(Arrays.asList(lis));
    return max; 
}