Skip to content
View adzierzanowski's full-sized avatar
🙃
the cake is a lie
🙃
the cake is a lie
4 followers · 1 following

Achievements

Achievement: Arctic Code Vault Contributor

Achievements

Achievement: Arctic Code Vault Contributor

Block or report adzierzanowski

Block user

Prevent this user from interacting with your repositories and sending you notifications. Learn more about blocking users.

You must be logged in to block users.

Maximum 250 characters. Please don't include any personal information such as legal names or email addresses. Markdown supported. This note will be visible to only you.
Report abuse

Contact GitHub support about this user’s behavior. Learn more about reporting abuse.

Report abuse
adzierzanowski/README.md

A little feed for thought or at least a fun fact:

Timeline of solving the maximum subarray problem

$$ \begin{gather*} \text{Given an array of numbers $\;A[1..n]$, find} \newline \displaystyle \max\left\{\sum_{i=k}^m A[i]:\quad 1\le k\le m\le n\right\} \end{gather*} $$

timeline
    1977: Problem and solution proposed by Ulf Grenander
    : Better performing algorithm proposed by Michael Shamos
    1978: .
    1979: .
    1980: .
    1981: .
    1982: .
    1983: .
    1984: Best possible algorithm published by Jay Kadane
Loading
Author Occupation Figured out the solution... Time complexity
Grenander mathematician, statistician, professor $O(n^2)$
Shamos comp-scientist, mathematician, professor overnight $O(n\;\log\;n)$
Kadane statistician, professor in a minute $O(n)$

The $O(n)$ algorithm:

def max_subarray(arr):
    best = float('-inf')
    current = 0
    for num in arr:
        current = max(num, current + num)
        best = max(best, current)
    return best

Obvious, right?

Pinned Loading

  1. volcano volcano Public

    libusb-based driver for Modecom Volcano Lanparty RGB keyboard

    C 5 3

  2. zasm zasm Public

    Zilog Z80 Assembler

    C

  3. gta2-map-editor gta2-map-editor Public

    In-browser GTA2 map editor

    TypeScript 1

  4. argparser argparser Public

    Simple, straightforward C command-line argparser

    C

  5. ps2-to-usb ps2-to-usb Public

    STM32 PS/2 to USB converter for keyboard

    C 6 6

  6. timg timg Public

    Display an image in terminal

    Python 28 4