Подтвердить что ты не робот

Потенциальное решение O (n) для наиболее долгого возрастания подпоследовательности

Я пытался ответить на эту проблему, используя только рекурсию (динамическое программирование) http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Из статьи и вокруг SO я понимаю, что наиболее эффективным существующим решением является O (nlgn). Мое решение - O (N), и я не могу найти случай, когда он терпит неудачу. Я включаю unit test случаи, которые я использовал.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class LongestIncreasingSubseq {

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        getLongestSubSeq(arr);
    }

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> indices = longestRecursive(arr, 0, arr.length-1);
        List<Integer> result = new ArrayList<>();
        for (Integer i : indices) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        return result;
    }

    private static List<Integer> longestRecursive(int[] arr, int start, int end) {
        if (start == end) {
            List<Integer> singleton = new ArrayList<>();
            singleton.add(start);
            return singleton;
        }

        List<Integer> bestRightSubsequence = longestRecursive(arr, start+1, end); //recursive call down the array to the next start index
        if (bestRightSubsequence.size() == 1 && arr[start] > arr[bestRightSubsequence.get(0)]) {
            bestRightSubsequence.set(0, start); //larger end allows more possibilities ahead
        } else if (arr[start] < arr[bestRightSubsequence.get(0)]) {
            bestRightSubsequence.add(0, start); //add to head
        } else if (bestRightSubsequence.size() > 1 && arr[start] < arr[bestRightSubsequence.get(1)]) {
            //larger than head, but still smaller than 2nd, so replace to allow more possibilities ahead
            bestRightSubsequence.set(0, start); 
        }

        return bestRightSubsequence;
    }

    @Test
    public void test() {
        int[] arr1 = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        int[] arr2 = {7, 0, 9, 2, 8, 4, 1};
        int[] arr3 = {9, 11, 2, 13, 7, 15};
        int[] arr4 = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int[] arr5 = {1, 2, 9, 4, 7, 3, 11, 8, 14, 6};
        assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 4, 6, 9, 11, 15));
        assertEquals(getLongestSubSeq(arr2), Arrays.asList(0, 2, 8));
        assertEquals(getLongestSubSeq(arr3), Arrays.asList(9, 11, 13, 15));
        assertEquals(getLongestSubSeq(arr4), Arrays.asList(10, 22, 33, 50, 60, 80));
        assertEquals(getLongestSubSeq(arr5), Arrays.asList(1, 2, 4, 7, 11, 14));
    }

}

Стоимость строго O (n) из-за отношения T (n) = T (n-1) + O (1) = > T (n) = O (n)

Может ли кто-нибудь найти случай, когда это не удается, или какие-либо ошибки там? Большое спасибо.

UPDATE: Спасибо всем за то, что я указал на свою ошибку в предыдущей реализации. Итоговый код, приведенный ниже, передает все тестовые примеры, которые он использовал для отказа.

Идея состоит в том, чтобы перечислить (вычислить) все возможные возрастающие подпоследовательности (каждый начинается с индекса я от 0 до N.length-1) и выбирает самую длинную подпоследовательность. Я использую memoization (используя хэш-таблицу), чтобы избежать перерасчета уже вычисленных подпоследовательностей - поэтому для каждого начального индекса мы только вычислим все возрастающие подпоследовательности один раз.

Однако я не уверен, как формально получить временную сложность в этом случае - я был бы признателен, если кто-нибудь сможет пролить свет на это. Большое спасибо.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.junit.Test;

public class LongestIncreasingSubsequence {

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> longest = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            List<Integer> candidate = longestSubseqStartsWith(arr, i);
            if (longest.size() < candidate.size()) {
                longest = candidate;
            }
        }

        List<Integer> result = new ArrayList<>();
        for (Integer i : longest) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        cache = new HashMap<>(); //new cache otherwise collision in next use - because object is static
        return result;
    }

    private static Map<Integer, List<Integer>> cache = new HashMap<>();
    private static List<Integer> longestSubseqStartsWith(int[] arr, int startIndex) {
        if (cache.containsKey(startIndex)) { //check if already computed
            //must always return a clone otherwise object sharing messes things up
            return new ArrayList<>(cache.get(startIndex)); 
        }

        if (startIndex == arr.length-1) {
            List<Integer> singleton = new ArrayList<>();
            singleton.add(startIndex);
            return singleton;
        }

        List<Integer> longest = new ArrayList<>();
        for (int i = startIndex + 1; i < arr.length; i++) {
            if (arr[startIndex] < arr[i]) {
                List<Integer> longestOnRight = longestSubseqStartsWith(arr, i);
                if (longestOnRight.size() > longest.size()) {
                    longest = longestOnRight;
                }
            }
        }

        longest.add(0, startIndex);
        List<Integer> cloneOfLongest = new ArrayList<>(longest);
        //must always cache a clone otherwise object sharing messes things up
        cache.put(startIndex, cloneOfLongest); //remember this subsequence
        return longest;
    }

    @Test
    public void test() {
        int[] arr1 = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        int[] arr2 = {7, 0, 9, 2, 8, 4, 1};
        int[] arr3 = {9, 11, 2, 13, 7, 15};
        int[] arr4 = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int[] arr5 = {1, 2, 9, 4, 7, 3, 11, 8, 14, 6};
        int[] arr6 = {0,0,0,0,0,0,1,1,1,1,2,3,0,0,0,1,1,0,1,1,0,1,0,3};
        int[] arr7 = {0,1,2,0,1,3};
        int[] arr8 = {0,1,2,3,4,5,1,3,8};
        assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 4, 6, 9, 13, 15));
        assertEquals(getLongestSubSeq(arr2), Arrays.asList(0, 2, 8));
        assertEquals(getLongestSubSeq(arr3), Arrays.asList(9, 11, 13, 15));
        assertEquals(getLongestSubSeq(arr4), Arrays.asList(10, 22, 33, 50, 60, 80));
        assertEquals(getLongestSubSeq(arr5), Arrays.asList(1, 2, 4, 7, 11, 14));
        assertEquals(getLongestSubSeq(arr6), Arrays.asList(0,1,2,3));
        assertEquals(getLongestSubSeq(arr7), Arrays.asList(0,1,2,3));
        assertEquals(getLongestSubSeq(arr8), Arrays.asList(0, 1, 2, 3, 4, 5, 8));
    }

    public static void main(String[] args) {
        int[] arr1 = {7, 0, 9, 2, 8, 4, 1};
        System.out.println(getLongestSubSeq(arr1));
    }

}
4b9b3361

ОТВЕТЫ

Ответ 1

В этом тестовом случае ваша программа не работает

int[] arr5 = {0,0,0,0,0,0,1,1,1,1,2,3,0,0,0,1,1,0,1,1,0,1,0,3};

Ваш результат [0, 1, 3] Не должно быть [0,1,2,3]

Ответ 2

Сейчас я попробовал свой алгоритм, используя следующий тестовый пример:

 @Test
    public void test() {

      int[] arr1 = {0,1,2,3,4,5,1,3,8};
      assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 1, 2, 3, 4, 5, 8));
    }

и он не удался, так как он выдавал выходные данные {1, 3, 8} EDITED согласно вашему комментарию.

Ответ 3

Извините, что являюсь носителем плохих новостей, но на самом деле это O (n 2). Я не уверен, что у вас было что-то более формальное, но вот мой анализ:

consider the case when the input is sorted in descending order
  (longestRecursive is never executed recursively, and the cache has no effect)

getLongestSubSeq iterates over the entire input -> 1:n
  each iteration calls longestRecursive
  longestRecursive compares arr[startIndex] < arr[i] for startIndex+1:n -> i - 1

Таким образом, сравнение arr [startIndex] < arr [i] имеет ровно сумму (i - 1, 1, n) = n * (n - 1)/2 раз, что, конечно, O (n 2). Вы можете принудительно использовать максимальный объем кэша, отправив вход, отсортированный по возрастанию. В этом случае getLongestSubSeq будет вызывать longestRecursive n раз; первый из них вызовет n - 1 рекурсивных вызовов, каждый из которых приведет к промаху в кеше и выполнит я - 1 сравнения arr [startIndex] < arr [i], потому что ничего не помещается в кеш, пока рекурсия не начнет разматываться. Количество сравнений точно такое же, как в примере, когда мы обошли кеш. Фактически, количество сравнений всегда одинаково; введение инверсий во входные данные просто заставляет код торговать рекурсиями для итерации.

Ответ 4

Это алгоритм O (n ^ 2). Потому что есть две петли. Второй цикл скрыт внутри вызова метода.

Это первый цикл: for (int i = 0; i < arr.length; i++). Внутри этого цикла вы вызвали longestSubseqStartsWith(arr, i);. Посмотрите на реализацию longestSubseqStartWith, мы видим for (int i = startIndex + 1; i < arr.length; i++)

Ответ 5

Это мое потенциальное решение O (N) в python3.x, если что-то не так, исправьте его:

l = list(map(int,input().split()))
t = []
t2 = []
m = 0
for i in l:
    if(len(t)!=0):
        if(t[-1]<=i):
            if(t[-1]!=1):
                 t.append(i)
        else:
            if(len(t)>m):
                t2 = t
                m = len(t)
            t = [i]
    else:
        t.append(i)
print(t2,len(t2))