When arrays make me cry

,

In a previous article we quickly glance through array fundamentals. We saw how array are presented in RAM, the difference between static and dynamic arrays and how an array can be ued to build a data structure called stack. Here we are going to dive a bit more deeper into different algortihmic pattern that how can used when dealing with arrays.

The Kadane’s algorithm

Imagine you have a list of numbers, something like daily changes in your bank account. We have some positive (you earned money) and some negative (you spent money). You want to find the best consecutive sequence of days where your total gain was the highest. This is exactly what the Kadane’s Algorithm does. Instead of checking every possible sequence (which would be slow), it scans the list just once. At each step, it asks:

  • Is it better to start a new sequence here?
  • Or to add this number to the sequence I’m already building?”

It keeps track of the highest sum it has seen so far and, by the end of the list, we get our answer.

This algorithm while simple is widely used in finance, signal processing, or anywhere you need to find the “best contiguous segment” in a series of numbers.

The brute force

In the leetcode language, problem should be framed as followed.

Find a non-empty sub-array with the largest sum

Given the array [4, -1, 2, -7, 3, 4] we can quikcly find a brute force approach using two pointers i and j.

1
2
3
4
5
6
7
8
9
10
def brut_force(nums: list[int]) -> int:
    max_sum = nums[0]

    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)

    return max_sum

Please feel free to play around with the embedded python tutor below.

The kadane’s way

The idea behind the kadane’s algorithm is pretty simple. If your sum is below 0. Reset your max to 0 and keep adding the element of the list until the end. The code will look like this.

1
2
3
4
5
6
7
8
9
def kadane(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = 0

    for num in nums:
        current_sum = max(0, current_sum + num)
        max_sum = max(current_sum, 0)

    return max_sum

To practice