java - steps - memoization dynamic programming
Solución potencial de O(n) a la subsecuencia cada vez mayor. (5)
Estaba tratando de responder a este problema, usando solo recursión (programación dinámica) http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Desde el artículo, y alrededor de SO, me doy cuenta de que la solución existente más eficiente es O (nlgn). Mi solución es O (N), y no puedo encontrar un caso que falle. Incluyo casos de prueba unitaria que utilicé.
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));
}
}
El costo es estrictamente O (n) debido a la relación T (n) = T (n-1) + O (1) => T (n) = O (n)
¿Alguien puede encontrar un caso en el que esto falle, o cualquier error que haya? Muchas gracias.
ACTUALIZACIÓN: Gracias a todos por señalar mi error en la implementación anterior. El código final a continuación pasa todos los casos de prueba que solían fallar.
La idea es enumerar (calcular) todas las subsecuencias en aumento posibles (cada una comienza desde el índice i desde 0 hasta N.length-1) y seleccionar la subsecuencia más larga. Utilizo la memorización (usando una tabla hash) para evitar recálputos de subsecuencias ya calculadas, por lo que para cada índice de inicio solo calculamos todas las subsecuencias crecientes una vez.
Sin embargo, no estoy seguro de cómo derivar formalmente la complejidad del tiempo en este caso; le agradecería que alguien pudiera aclarar esto. Muchas gracias.
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));
}
}
Ahora mismo probé su algoritmo usando el siguiente caso de prueba:
@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));
}
y ha fallado, ya que da salida {1, 3, 8} EDITADA según su comentario.
Esta es mi solución de potencial O (N) en 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))
Este es un algoritmo O (n ^ 2). Porque hay dos bucles. El segundo bucle está oculto dentro de una llamada de método.
Este es el primer bucle: for (int i = 0; i < arr.length; i++) . Dentro de este bucle longestSubseqStartsWith(arr, i); . Observe la implementación de longestSubseqStartWith que vemos for (int i = startIndex + 1; i < arr.length; i++)
Lamento ser el portador de malas noticias, pero esto es en realidad O (n 2 ). No estoy seguro de si tuvieras algo más formal en mente, pero aquí está mi análisis:
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
Por lo tanto, la comparación arr [startIndex] <arr [i] se produce exactamente suma (i - 1, 1, n) = n * (n - 1) / 2 veces, que es ciertamente O (n 2 ). Puede forzar el uso máximo de caché enviando una entrada que esté ordenada en forma ascendente. En este caso, getLongestSubSeq llamaría longestRecursive n times; el primero de ellos desencadenaría n - 1 llamadas recursivas, cada una de las cuales provocaría una falta de memoria caché y ejecutaría las comparaciones i - 1 arr [startIndex] <arr [i] porque no se coloca nada en la caché hasta que la recursión comienza a desenrollarse. El número de comparaciones es exactamente el mismo que en el ejemplo en el que omitimos el caché. De hecho, el número de comparaciones es siempre el mismo; la introducción de inversiones en la entrada simplemente hace que el código intercambie recursiones por iteración.
Tu programa falla en este caso de prueba
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};
Su resultado [0, 1, 3] No debería ser [0,1,2,3]