All New

user:thomas gists created by user

title:mygist gists with given title

filename:myfile.txt gists having files with given name

extension:yml gists having files with given extension

language:go gists having files with given language

topic:homelab gists with given topic

Register

Login


All New Register Login

linkjobai

Joined 5 days ago

Recently created
Least recently created
Recently updated
Least recently updated
All gists 1

linkjobai / Kadane's Algorithm: Maximum Subarray in One Pass

0 likes
0 forks
1 files
Last active 5 days ago
Interview prep notes
interview

Kadane's Algorithm: Maximum Subarray in One Pass

Maximum Subarray (LeetCode 53) asks for the largest sum of any contiguous subarray. Brute force checks every pair of endpoints, which is O(n²). Kadane's algorithm does it in O(n) with O(1) memory.

The insight

At each index, the best subarray ending here either extends the previous best one or starts fresh. You start fresh whenever the running sum has gone negative, because a negative prefix can only make things worse.

def max_subarray(nums):
Newer Older

Powered by Opengist ⋅ Load: 13ms⋅

English
Čeština Deutsch English Español Français Magyar Italiano 日本語 Polski Português Русский Türkçe Українська 中文 繁體中文