Log in from a computer to take this course

You'll need to log in from a computer to start Technical Interview Practice with Python. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

apple storegoogle store
Learn

Our last solution had a cubic time complexity: O(N^3).

One iteration for the length of the list O(N), inside another iteration for the length of the list O(N^2), inside the inner loop, we copied a sub-list: O(N^3).

Let’s optimize using an important concept: We don’t always need to create every possible outcome to know what’s best.

Do we need to make every sub-list? No! We can visit each value within the list and keep a running tally of sums.

Let’s see what information we can gather in a single pass:

# <> will mark the current element nums = [1, -7, 2, 15, -11, 2] most_seen = 0 current_max_sub_sum = 0 [<1>, -7, 2, 15, -11, 2] most_seen = 1 current_max_sub_sum = 1 [1, <-7>, 2, 15, -11, 2] most_seen = 1 current_max_sub_sum = -6 # our sum is negative # anything positive which comes after # will be better without this "sub-list" # reset current max to 0! current_max_sub_sum = 0 [1, -7, <2>, 15, -11, 2] most_seen = 2 current_max_sub_sum = 2 [1, -7, 2, <15>, -11, 2] most_seen = 17 current_max_sub_sum = 17 [1, -7, 2, 15, <-11>, 2] most_seen = 17 current_max_sub_sum = 6 # current sum went down, but not negative # no need to reset! [1, -7, 2, 15, -11, <2>] most_seen = 17 current_max_sub_sum = 8

Moving through the list just once is sufficient to find the maximum contiguous sub-sum.

Instructions

1.

Write a function maximum_sub_sum() which has a single parameter: my_list.

maximum_sub_sum() should return the maximum sum of contiguous values in my_list.

Your solution should run in O(N) time and O(1) space!

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?