Una vez que conozca los elementos compartidos entre las dos listas, puede iterar sobre cada lista por separado para resumir los elementos entre los elementos compartidos, construyendo así una lista de sumas parciales. Estas listas tendrán la misma longitud para ambas listas de entrada, porque el número de elementos compartidos es el mismo.

La suma máxima de la ruta se puede encontrar tomando el máximo entre las dos listas para cada tramo entre valores compartidos:

 def max_sum_path(l1, l2): shared_items = set(l1) & set(l2) def partial_sums(lst): result = [] partial_sum = 0 for item in lst: partial_sum += item if item in shared_items: result.append(partial_sum) partial_sum = 0 result.append(partial_sum) return result return sum(map(max, partial_sums(l1), partial_sums(l2)))

Complejidad temporal: solo iteramos una vez sobre cada lista (la iteración sobre las listas más cortas de sumas parciales es irrelevante aquí), por lo que este código es lineal en la longitud de las listas de entrada. Sin embargo, como usted y Kelly Bundy han notado, su propio algoritmo en realidad tiene la misma complejidad de tiempo, excepto por la parte de clasificación de elementos comunes, que no parece ser demasiado relevante para los casos de prueba dados.

Entonces, como conclusión general, si su objetivo es solo hacer que su código sea lo suficientemente rápido para pasar ciertos casos de prueba, puede ser mejor perfilar la ejecución para encontrar los sumideros de tiempo en la implementación real en lugar de preocuparse por los peores escenarios teóricos.

El problema dice "apuntar a la complejidad del tiempo lineal", que es una gran pista de que cosas como los bucles anidados no funcionarán ( index son bucles O (n) anidados aquí y sort() es O (n log (n)) cuando hay muchos valores duplicados entre las listas de entrada).

Esta respuesta muestra cómo puede almacenar en caché las llamadas .index repetidas y usar compensaciones de inicio desde el último fragmento para reducir la complejidad.

Como también indica la respuesta vinculada, itertools.islice no es apropiado aquí porque atraviesa desde el principio de la lista. En su lugar, utilice el corte nativo. Esto, junto con las modificaciones al index anterior, le brinda una complejidad lineal rítmica general, lineal en la mayoría de las entradas.

Para el contexto, aquí está mi enfoque, que no es tan diferente del suyo, aunque guardo en caché los índices y evito ordenarlos.

Empecé formulando el problema como un gráfico acíclico dirigido con la idea de buscar la suma máxima de caminos:

 +---> [0, 2, 3] ---+ +---> [10, 12] [0] ---| |---> [7] ---| +---> [1, 5] ------+ +---> [8]

También podríamos sumar los valores de cada nodo para mayor claridad:

 +---> 5 ---+ +---> 22 0 ---| |---> 7 ---| +---> 6 ---+ +---> 8

El diagrama anterior revela que una solución codiciosa será óptima, dadas las restricciones de unicidad. Por ejemplo, comenzando desde la raíz, solo podemos elegir la ruta de valor 5 o 6 para llegar a 7. Se garantiza que el mayor de los dos, 6, sea parte de la ruta de peso máximo, así que lo tomamos.

Ahora, la pregunta es solo cómo implementar esta lógica. Volviendo a las listas, aquí hay una entrada más sustancial con formato y anotaciones para ayudar a motivar un enfoque:

 [1, 2, 4, 7, 8, 10, 14, 15 ] [ 4, 8, 9, 11, 12, 15, 90] ^ ^ ^ | | |

Esto ilustra cómo se alinean los índices vinculados. Nuestro objetivo es iterar sobre cada fragmento entre los enlaces, tomando la suma mayor de las dos sublistas:

 [1, 2, 4, 7, 8, 10, 14, 15 ] [ 4, 8, 9, 11, 12, 15, 90] ^~~^ ^ ^~~~~~~~~~~~~~~~^ ^^ 0 1 2 3 <-- chunk number

El resultado esperado para la entrada anterior debe ser 3 + 4 + 7 + 8 + 32 + 15 + 90 = 159, tomando todos los valores de enlace más la suma de la sublista de la lista superior para los fragmentos 0 y 1 y la lista inferior para los fragmentos 2 y 3.

Aquí hay una implementación bastante detallada, pero con suerte fácil de entender; Puedes visitar el hilo para ver soluciones más elegantes:

 def max_sum_path(a, b): b_idxes = {k: i for i, k in enumerate(b)} link_to_a = {} link_to_b = {} for i, e in enumerate(a): if e in b_idxes: link_to_a[e] = i link_to_b[e] = b_idxes[e] total = 0 start_a = 0 start_b = 0 for link in link_to_a: # dicts assumed sorted, Python 3.6+ end_a = link_to_a[link] end_b = link_to_b[link] total += max(sum(a[start_a:end_a]), sum(b[start_b:end_b])) + link start_a = end_a + 1 start_b = end_b + 1 return total + max(sum(a[start_a:]), sum(b[start_b:]))

Su algoritmo es realmente rápido, solo que su implementación es lenta.

Las dos cosas que hacen que tome el tiempo total O(n²):

• l1.index(item) siempre busca desde el principio de la lista. Debería ser l1.index(item, new_start1) .
• itertools.islice(l1, new_start1, ...) crea un iterador para l1 e itera sobre los primeros elementos new_start1 antes de llegar a los elementos que desea. Así que solo usa un segmento de lista normal en su lugar.

Entonces es solo O (n log n) para la clasificación y O (n) para todo lo demás. Y la clasificación O (n log n) es rápida, fácilmente podría tomar menos tiempo que la parte O (n) para cualquier entrada permitida e incluso más grandes.

Aquí está la versión reescrita, se acepta en aproximadamente 6 segundos, al igual que las soluciones de las otras respuestas.

 def max_sum_path(l1:list, l2:list): common_items = list(set(l1).intersection(l2)) if not common_items: return max(sum(l1), sum(l2)) common_items.sort() s = 0 new_start1 = 0 new_start2 = 0 s1 = 0 s2 = 0 for item in common_items: next_start1 = l1.index(item, new_start1) # changed next_start2 = l2.index(item, new_start2) # changed s1 = sum(l1[new_start1 : next_start1]) # changed s2 = sum(l2[new_start2 : next_start2]) # changed new_start1 = next_start1 # changed new_start2 = next_start2 # changed s += max(s1, s2) s1 = sum(l1[new_start1:]) # changed s2 = sum(l2[new_start2:]) # changed s += max(s1, s2) return s

O podría usar iteradores en lugar de índices. Aquí está su solución reescrita para hacer eso, también se acepta en aproximadamente 6 segundos:

 def max_sum_path(l1:list, l2:list): common_items = sorted(set(l1) & set(l2)) s = 0 it1 = iter(l1) it2 = iter(l2) for item in common_items: s1 = sum(iter(it1.__next__, item)) s2 = sum(iter(it2.__next__, item)) s += max(s1, s2) + item s1 = sum(it1) s2 = sum(it2) s += max(s1, s2) return s

Combinaría las últimas cuatro líneas en una, simplemente lo dejaría como lo tenía para que sea más fácil de comparar.

Esto se puede hacer en un solo paso en el tiempo de ejecución O(n) y la complejidad del espacio O(1) . Todo lo que necesita son dos punteros para atravesar ambas matrices en paralelo y dos valores de ruta.

Incrementa el puntero al elemento más pequeño y agrega su valor a su ruta. Cuando encuentra un elemento común, lo agrega a ambas rutas y luego establece ambas rutas al valor máximo.

 def max_sum_path(l1, l2): path1 = 0 path2 = 0 i = 0 j = 0 while i < len(l1) and j < len(l2): if l1[i] < l2[j]: path1 += l1[i] i += 1 elif l2[j] < l1[i]: path2 += l2[j] j += 1 else: # Same element in both paths path1 += l1[i] path2 += l1[i] path1 = max(path1, path2) path2 = path1 i += 1 j += 1 while i < len(l1): path1 += l1[i] i += 1 while j < len(l2): path2 += l2[j] j += 1 return max(path1, path2)

Puntos de referencia

En la pestaña Discurso , puede hacer clic en "Mostrar casos de prueba de Kata" (una vez que resolvió el kata) para ver su generador de casos de prueba. Lo usé para comparar las soluciones publicadas hasta ahora, así como una mía. Unas pocas docenas de rondas, ya que los casos de prueba son bastante aleatorios, lo que provoca una gran fluctuación en el tiempo de ejecución. En cada ronda, todos los casos de prueba generados se entregaron a todas las soluciones (por lo que en cada ronda, todas las soluciones obtuvieron los mismos casos de prueba).

Y también el peor caso de Kelly Bundy para clasificar el conjunto de valores comunes:

Seguirá el código.