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.

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.