Search code examples
pythonalgorithmsublistmaximize

Find maximum sum of sublist in list of positive integers under O(n^2) of specified length Python 3.5

For one of my programming questions, I am required to define a function that accepts two variables, a list of length l and an integer w. I then have to find the maximum sum of a sublist with length w within the list.

Conditions:

1<=w<=l<=100000

Each element in the list ranges from [1, 100]

Currently, my solution works in O(n^2) (correct me if I'm wrong, code attached below), which the autograder does not accept, since we are required to find an even simpler solution.

My code:

def find_best_location(w, lst):
    best = 0
    n = 0
    while n <= len(lst) - w:
        lists = lst[n: n + w]
        cur = sum(lists)
        best = cur if cur>best else best
        n+=1

    return best

If anyone is able to find a more efficient solution, please do let me know! Also if I computed my big-O notation wrongly do let me know as well!

Thanks in advance!

Solution

  • 1) Find sum current of first w elements, assign it to best.
    2) Starting from i = w: current = current + lst[i]-lst[i-w], best = max(best, current).
    3) Done.