My question is about this kata on Codewars. Function takes two sorted lists with distinct elements as argument, which they might or might not have common items. Task is find the maximum path sum. While finding the sum if there any common items you can choose to change your path to the other list. The given example is like this:
list1 = [0, 2, 3, 7, 10, 12]
list2 = [1, 5, 7, 8]
0->2->3->7->10->12 => 34
0->2->3->7->8 => 20
1->5->7->8 => 21
1->5->7->10->12 => 35 (maximum path)
Actually i solve the kata but my code doesn't match the performance criteria so i get execution timed out. What can i do for it? How can i improve?
Here is my solution:
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:
s1 = sum(itertools.islice(l1, new_start1, l1.index(item)))
s2 = sum(itertools.islice(l2, new_start2, l2.index(item)))
new_start1 = l1.index(item)
new_start2 = l2.index(item)
s += max(s1, s2)
s1 = sum(itertools.islice(l1, new_start1, len(l1)))
s2 = sum(itertools.islice(l2, new_start2, len(l2)))
s += max(s1, s2)
return s
from Recent Questions - Stack Overflow https://ift.tt/3puYtng
https://ift.tt/eA8V8J
No comments:
Post a Comment