find maximum length sublist with sum 60s 60 present in a given list

Solutions on MaxInterview for find maximum length sublist with sum 60s 60 present in a given list by the best coders in the world

showing results for - "find maximum length sublist with sum 60s 60 present in a given list"
Miranda
14 Jul 2020
1def findMaxLenSublist(A, S):
2 
3    # create an empty dictionary to store the ending index of the first
4    # sublist having some sum
5    dict = {}
6 
7    # insert `(0, -1)` pair into the set to handle the case when a
8    # sublist with sum `S` starts from index 0
9    dict[0] = -1
10 
11    sum = 0
12 
13    # `length` stores the maximum length of sublist with sum `S`
14    length = 0
15 
16    # stores ending index of the maximum length sublist having sum `S`
17    ending_index = -1
18 
19    # traverse the given list
20    for i in range(len(A)):
21 
22        # sum of elements so far
23        sum += A[i]
24 
25        # if the sum is seen for the first time, insert the sum with its
26        # into the dictionary
27        if sum not in dict:
28            dict[sum] = i
29 
30        # update length and ending index of the maximum length sublist
31        # having sum `S`
32        if sum - S in dict and length < i - dict[sum - S]:
33            length = i - dict[sum - S]
34            ending_index = i
35 
36    # print the sublist
37    print((ending_index - length + 1, ending_index))
similar questions