beingsde
Sign In
Back to all DSA patterns
Array•Pattern: Kadane's / Dynamic Programming•Medium

Maximum subarray sum (Kadane's Algorithm)

Problem Intuition & Objective

Find the contiguous subarray with the largest sum.

Time ComplexityO(n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Kadane's: at each index decide whether to extend the current subarray or start a new one.

Core Invariants & Edge Cases

  • currentMax = max(num, currentMax + num)
  • globalMax tracks the best seen so far
  • Handles all-negative arrays by returning the largest single element
Previous ProblemProduct of array except selfNext Problem 3Sum — find all unique triplets that sum to zero

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.