DEV Community: Joscelyn Stancek

max subarray problem and kadane's algorithm

Joscelyn Stancek — Tue, 13 Aug 2024 21:29:17 +0000

The max subarray problem and its history

In the late 1970s, Swedish mathematician Ulf Grenander had been discussing a problem: how can you analyze a 2D array of image data more efficiently than brute force? Computers then were slow and pictures were large relative to the RAM. To exacerbate things, in the worst case scenario brute force took O(n^6) time (sextic time complexity).

First, Grenandier simplified the question: Given just a one dimensional array of numbers, how would you most efficiently find the contiguous subarray with the largest sum?

Brute Force: A Naive Approach with Cubic Time Complexity

Brute force, it would be half as much time to analyze a 1D array as a 2D array, so O(n^3) to examine every possible combination (cubic time complexity).

def max_subarray_brute_force(arr):
    max_sum = arr[0] # assumes arr has a length

    # iterate over all possible subarrays
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            current_sum = 0
            # sum the elements of the subarray arr[i:j+1]
            for k in range(i, j + 1):
                current_sum += arr[k]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

print(max_subarray_brute_force([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

Grenander’s O(n²) Optimization: A Step Forward

Grenander improved it to O(n^2) solution. I couldn't find his code in my research, but my guess is he simply got rid of the innermost loop that adds up all of the numbers between the two indices. Instead, we can keep a running sum while iterating over the subarray, thus reducing the number of loops from three to two.

def max_subarray_optimized(arr):
    max_sum = arr[0]  # assumes arr has a length

    # iterate over all possible starting points of the subarray
    for i in range(len(arr)):
        current_sum = 0
        # sum the elements of the subarray starting from arr[i]
        for j in range(i, len(arr)):
            current_sum += arr[j]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

Shamos's Divide and Conquer: Splitting the Problem for O(n log n)

Grenander showed the problem to computer scientist Michael Shamos. Shamos thought about it for one night and came up with a divide and conquer method which is O(n log n).

It's quite clever. The idea is to divide the array into two halves, then recursively find the maximum subarray sum for each half as well as the subarray crossing the midpoint.


def max_crossing_sum(arr, left, mid, right):
    # left of mid
    left_sum = float('-inf')
    current_sum = 0
    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        left_sum = max(left_sum, current_sum)

    # right of mid
    right_sum = float('inf')
    current_sum = 0
    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        right_sum = max(right_sum, current_sum)

    # sum of elements on the left and right of mid, which is the maximum sum that crosses the midpoint
    return left_sum + right_sum

def max_subarray_divide_and_conquer(arr, left, right):
    # base case: only one element
    if left == right:
        return arr[left]

    # find the midpoint
    mid = (left + right) // 2

    # recursively find the maximum subarray sum for the left and right halves
    left_sum = max_subarray_divide_and_conquer(arr, left, mid)
    right_sum = max_subarray_divide_and_conquer(arr, mid + 1, right)
    cross_sum = max_crossing_sum(arr, left, mid, right)

    # return the maximum of the three possible cases
    return max(left_sum, right_sum, cross_sum)

def max_subarray(arr):
    return max_subarray_divide_and_conquer(arr, 0, len(arr) - 1)


print(max_subarray([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

This reduces the time complexity to O(nlogn) time because first the array is divided into two halves (O(logn)) and then finding the max crossing subarray takes O(n)

Kadane’s Algorithm: The Elegant O(n) Solution

Stastician Jay Kadane looked at the code and immediately identified that Shamos's solution failed to use the contiguity restraint as part of the solution.

Here's what he realized

-If an array has only negative numbers, then the answer will always be the single largest number in the array, assuming we're not allowing empty subarrays.

-If an array only has positive numbers, the answer will always be to add up the entire array.

-If you have an array of both positive and negative numbers, then you can traverse the array step by step. If at any point the number you're looking at is bigger than the sum of all the numbers that came before it, the solution cannot include any of the previous numbers. Thus, you start a new sum from the current number, while keeping track of the maximum sum encountered so far.



maxSubArray(nums):
    # avoiding type errors or index out of bounds errors
    if nums is None or len(nums) == 0:
        return 0


    max_sum = nums[0]  # max sum can't be smaller than any given element
    curr_sum = 0

    # Kadane's algorithm
    for num in nums:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(curr_sum, max_sum)
    return max_sum

LeetCode Problems to Practice

What I love about this algorithm is it can be applied to lots of other problems. Try adapting it to solve these LeetCode problems:

Robot vs Zombies Live Stream E07

Joscelyn Stancek — Tue, 27 Oct 2020 22:53:54 +0000

We start adding items to the game in the form of a key and randomly placing it on the game board.

Robot vs Zombies Live Stream E06

Joscelyn Stancek — Tue, 06 Oct 2020 21:30:34 +0000

We started by giving the wall tiles and building tiles an object of information using OOP. Then we work to encapsulate our large function generateRooms. Finally we add sound effects that start whenever the player goes inside.

Robot vs Zombies Live Stream E05

Joscelyn Stancek — Tue, 29 Sep 2020 02:38:50 +0000

We add sound effects for when the robot walks or runs into walls. Then we create a mute button. Finally, we chat with our artist Ben about next steps for the tiles and buildings.

Robot vs Zombies Live Stream E04

Joscelyn Stancek — Tue, 22 Sep 2020 13:16:23 +0000

We use a little math to fix the problem with the viewport scrolling infinitely right. Then we add a border to the game, make the walls impassable, and add doors to the buildings.

My Three Favorite VS Code Extensions

Joscelyn Stancek — Thu, 17 Sep 2020 13:55:11 +0000

VS Code is by far my favorite code editor. It's free, it works on every OS, and it's easy to customize.

Here are my three favorite VS Code extensions.

1. Make your code better and more beautiful with ESLint and Prettier

I honestly don't know how I lived without these. ESLint is great at finding problems in your code that might lead to bugs. Prettier forces your code to adhere to certain style rules.

After installing Prettier via the extensions tab, I made it my default formatter by adding this to the main settings.json file:

  "[javascript]": {
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  },
  "[html]": {
    "editor.defaultFormatter": "esbenp.prettier-vscode"
  }
}

You can also do it through the GUI.

Then I set VS Code to format on save by adding this:

  "editor.formatOnSave": true,

Pro Tip: Prettier is opinionated. I agree with most of the default settings, but I prefer to use single quotes in JavaScript.

There are a few places I can make this change. At the largest scope, I can change it in the main settings.json file for all VS Code if I want all of my projects to follow this rule. In the middle scope, I can add it to my workspace settings if I want this rule for all projects in a given workspace. In the narrowest scope, I can just add the rule to this one project. Whichever settings file you add it too, the code will look like this: "prettier.singleQuote": true,

What if you want everyone on the team to have these settings but you want to keep the vscode directory in the gitignore?

Two choices:

Add the prettier settings to the package.json, in which case it will look like this:

  "prettier": {
    "singleQuote": true
  },

Create a .prettierrc file in the outermost directory and put the settings there. These are the settings that I like to add for my personal React projects:

{
  "printWidth": 80,
  "tabWidth": 4,
  "useTabs": true,
  "semi": true,
  "singleQuote": true,
  "trailingComma": "all",
  "bracketSpacing": true,
  "jsxBracketSameLine": true
}

And here's a list of all the settings you can change with Prettier:

prettier.arrowParens
prettier.bracketSpacing
prettier.endOfLine
prettier.htmlWhitespaceSensitivity
prettier.insertPragma
prettier.jsxBracketSameLine
prettier.jsxSingleQuote
prettier.printWidth
prettier.proseWrap
prettier.quoteProps
prettier.requirePragma
prettier.semi
prettier.singleQuote
prettier.tabWidth
prettier.trailingComma
prettier.useTabs
prettier.vueIndentScriptAndStyle
prettier.embeddedLanguageFormatting

2. Change the color with Peacock

When I have multiple projects open at once--say a back end and a front end--then having them instantly recognizable with different colors saves me precious seconds.

After installing it use Ctrl+Shift+P(Windows) or Cmd+Shift+P(Mac) to open the command palette. Type in "peacock," and if you're in a hurry choose "surprise me with a random color." You can also choose your own color and edit the list of favorite colors.

Pro Tip 1: add /vscode to your gitignore file or else everyone on your team will get your color settings.

Pro Tip 2: only want a little color? You can change your settings so that the color only affects certain parts of VS Code. Here, only the title bar is affected by Peacock.

I used the following in the settings.json file under the vscode directory to achieve this:

  "peacock.affectActivityBar": false,
  "peacock.affectStatusBar": false,
  "peacock.affectTitleBar": true

3. Pair program remotely with Live Share

Live Share allows multiple people to work on the same files at the same time. It basically turns your code into a Google Doc where you can see other people typing.

The benefit of this is that it's easier to pair program remotely. No one needs to worry about merge conflicts because you're editing everything together.

The host can even share their terminal and their local servers so everyone on the team can see and interact with them.

There are a few issues.

If you're both working on something on the front end you might get frustrated. That's because you can't see what renders on the screen if the other person is halfway through typing something.
Live Share is the best out there that I've seen but still I've had days where it disconnected every hour.

Pro Tip: if you want to make sure everyone gets credit in the git commits the host needs to add each person's name to the commit like so:

Co-authored-by: username <email>

Robot vs Zombies Live Stream E03

Joscelyn Stancek — Wed, 16 Sep 2020 21:56:57 +0000

Robot vs Zombies Live Stream E02

Joscelyn Stancek — Wed, 16 Sep 2020 21:52:23 +0000

Robot vs Zombies Live Stream E01

Joscelyn Stancek — Wed, 16 Sep 2020 21:46:28 +0000