#53EasyKadane's Algorithm

Maximum Subarray

Kadane's Algorithm — the elegance of tracking local vs global max.

AmazonMicrosoftGoogleAdobeLinkedIn

Problem Statement

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous part of the array.

Examples

Example 1

Input:nums = [-2,1,-3,4,-1,2,1,-5,4]
Output:6

Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Example 2

Input:nums = [1]
Output:1

Constraints

  • 1 ≤ nums.length ≤ 10⁵
  • -10⁴ ≤ nums[i] ≤ 10⁴

Solutions

1
Brute Force — All subarrays
TimeO(n²)SpaceO(1)

Try every possible subarray by iterating over all start and end indices. For each subarray, compute the sum. Track the maximum. O(n²) or O(n³) time.

Visual Animation
def maxSubArray(nums: list[int]) -> int:
    max_sum = float(@@0@@)
    n = len(nums)
    for i in range(n):
        current = 0
        for j in range(i, n):
            current += nums[j]
            max_sum = max(max_sum, current)
    return max_sum

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Dynamic Programming ConceptBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Kadane's Algorithm to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems