What should be the time complexity for the brute force solution described. Shouldn’t it be O(n^3) , as for each index of the array we add from 1 to n-1 , so O(n^2) for each element and then O(n^3) for the entire array.
The video mentions brute force as O(n^2).
I used this approach:
def find_max_sum_sublist(lst):
# Write your code here!
maximum = lst[0]
curr = 0
i = 0
while i != (len(lst)-1):
if lst[i] < 0:
if curr > maximum:
maximum = curr
curr = 0
else:
curr += lst[i]
i += 1
return maximum