Maximum Subarray - Practice Coding Problems

Maximum Subarray - Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 6

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

Example 2 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Array has only one element, so maximum subarray sum is 1

Example 3 — All Negative

$ Input: nums = [-2,-1]

› Output: -1

💡 Note: The subarray [-1] has the largest sum = -1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with positive and negative integers

Find Best Subarray

Identify contiguous elements with maximum sum

Return Sum

Output the maximum subarray sum

Key Takeaway

🎯 Key Insight: Reset running sum to zero whenever it becomes negative, as negative prefixes never help maximize the total sum

Asked in

G Google 45 a Amazon 38 M Microsoft 32 🍎 Apple 28

The key insight is that any subarray with a negative sum should be discarded since it would only reduce the sum of any larger subarray containing it. Kadane's Algorithm efficiently tracks the running sum and resets when it becomes negative, achieving optimal performance. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Kadane's Algorithm	O(n)	O(1)	Track running sum, reset when negative for optimal O(n) solution
Prefix Sum	O(n²)	O(n)	Use prefix sums to calculate any subarray sum in O(1)
Brute Force	O(n³)	O(1)	Check all possible subarrays and find maximum sum

Kadane's Algorithm — Algorithm Steps

Initialize max_sum and current_sum
For each element in array
Add element to current_sum
If current_sum < 0, reset to 0
Update max_sum if current_sum is larger

Visualization

Tap to expand

Step-by-Step Walkthrough

Iterate Once

Single pass through array

Track Running Sum

Add each element to current sum

Reset When Negative

Start fresh when sum becomes negative

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int maxSum = nums[0];
    int currentSum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        currentSum += nums[i];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        if (currentSum < 0) {
            currentSum = 0;
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array, visiting each element once

✓ Linear Growth

Space Complexity

O(1)

Only uses two variables to track current sum and maximum sum

✓ Linear Space

125.0K Views

Very High Frequency

~15 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Kadane's Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler