Weekly Coding Challenge: Maximum Subarray Sum using a version of Kadane’s Algorithm – written in Python

2 min read ~ Hello readers! It’s really important for me to continue my practice and learning. Every week, I block off 30 minutes, set a timer and choose a challenge from codewars. This helps me keep my skills sharp, see how other devs all over the planet would solve these problems, and take some leisure time to problem solve and be creative. Being able to see other solutions expands my mind for solving future problems in a clever and efficient way. Today, the problem set focuses on Python.

For those that are not familiar, this challenge uses a version of Kadane’s algorithm (one of my favorites!). If you are not familiar, this algorithm falls within the field of dynamic programming. This algorithm will help us find the largest sum possible in a continuous array of integers that can include negative numbers. Here is a link to learn more.

The maximum sum subarray problem consists in finding the maximum sum of a continuous subarray of integers that can include negative integers:

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
# should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

def max_sequence(arr):
    curSum = 0
    curMax = 0
    for numb in arr:
        tempNumb = int(numb)
        if (tempNumb + curSum > 0):
            curSum = curSum + tempNumb
            if curSum > curMax:
                curMax = curSum
        else:
            curSum = 0
    return curMax

When looking to define the max sequence, we can utilize our curSum to to determine when the sum of integers remains above 0. When that changes, we can check to see if that number is greater than the current max and replace it if necessary. If the number within the iteration added to the curSum falls into a negative number, we know that we are ready to reset our curSum back to 0 and continue with the procedure.

All solutions are also now on my GitHub profile if you want to check out all of the coding challenges I’ve completed so far!

All credit to problem sets goes to codewars