Max Subarray Sum — Problem Statement & Solution Guide

ArraysEasyTwo Pointers

TimeO(n)

SpaceO(1)

Problem Description

You are given an array of integers, which may be empty. Your task is to determine the largest possible sum that can be obtained by selecting a contiguous subsequence of the array. If the array contains no elements, the maximum sum is defined to be 0. The solution must consider all possible contiguous subarrays and return the maximum sum among them.

Input: The input consists of a single line containing the elements of the array separated by spaces. The array may be empty, in which case the line will be blank.

Output: Output a single integer representing the maximum contiguous subarray sum, or 0 if the array is empty.

The algorithm should run efficiently for large arrays, as the constraints allow up to 10^5 elements.

DSA Pattern Breakdown

"Max Subarray Sum"

easy

WHY DOES IT MATTER?

Kadane's pattern is essential because it transforms an exponential search space into a single linear scan, making it suitable for real-time analytics and large-scale data processing where performance is critical.

OPTIMIZATION CHALLENGE

The key insight is that the optimal subarray ending at index i depends only on the optimal subarray ending at i-1 and the current element, eliminating the need to recompute sums from scratch.

REAL-WORLD CONNECTION

Think of monitoring server load over time: you want the period with the highest cumulative load. Kadane's algorithm is like a sliding window that updates the best period on the fly, similar to how a load balancer might track peak traffic windows.

When explaining to an interviewer, emphasize the invariant: 'currentSum is the maximum sum of a subarray ending at the current index', and show how updating this invariant leads directly to the global maximum.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem of finding the maximum sum of a contiguous subarray is a classic example of dynamic programming that can be solved in linear time using Kadane's algorithm. The naive approach enumerates all possible subarrays, computing their sums with nested loops, leading to an O(n^2) or even O(n^3) time complexity depending on implementation; this quickly becomes infeasible for arrays with millions of elements. Kadane's algorithm observes that the maximum subarray ending at position i either extends the maximum subarray ending at i-1 or starts fresh at i, allowing us to maintain a running maximum and a current sum in a single pass, reducing both time to O(n) and space to O(1).

Interview Questions on This Problem

Q1How would you modify the algorithm if the array could contain only positive numbers?

If all numbers are positive, the maximum subarray is simply the entire array, so you can just sum all elements in O(n) time. This also serves as a sanity check for your implementation.

Q2What changes would you make to handle the case where the array can be empty or all negative?

Return 0 for an empty array as specified. For all-negative arrays, Kadane's algorithm naturally returns the largest (least negative) element because the current sum will reset to the element itself when it becomes negative.

Q3Can you explain how this problem relates to the maximum subarray problem in a circular array?

In a circular array, the maximum subarray might wrap around the end. The solution involves computing the maximum subarray normally and also the minimum subarray; the circular maximum is either the normal maximum or the total sum minus the minimum subarray, whichever is larger.

Examples

Example 1

Input

1 -2 3 5 -1 2

Output

Explanation: We examine all contiguous subarrays. The subarray [3, 5, -1, 2] has a sum of 9, which is the highest achievable. No other subarray yields a larger sum, so the answer is 9.

Example 2

Input

-5 -1 -3

Output

Explanation: All elements are negative, so any non‑empty subarray would produce a negative sum. The problem definition allows the empty subarray, whose sum is 0, which is therefore the maximum.

Example 3

Input

10 -3 2 1 -5 4

Output

Explanation: The subarray [10, -3, 2, 1] sums to 10. Any extension of this subarray decreases the total sum, and no other subarray achieves a sum greater than 10.

Example 4

Input

Output

Explanation: The array is empty, so by definition the maximum sum is 0.

Example 5

Input

1000000000 -1000000000 1000000000

Output

1000000000

Explanation: The best choice is the single element 1000000000. Adding any other element reduces the sum, so the maximum contiguous sum is 1000000000.

Constraints

0 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
The sum of all elements fits within a 64‑bit signed integer

Optimal Approach & Strategy

Iterate once through the array, maintaining a running sum that resets to zero when negative, and update the maximum sum seen. This is Kadane's algorithm, running in O(n) time and O(1) space.

Brute Force Approach

Enumerate every possible start and end index, compute the sum of each subarray, and track the maximum. This requires nested loops and recomputing sums, leading to O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) {
   if (nums.length === 0) return 0;
   let max_sum = nums[0];
   let current_sum = nums[0];
   for (let i = 1; i < nums.length; i++) {
       current_sum = Math.max(nums[i], current_sum + nums[i]);
       max_sum = Math.max(max_sum, current_sum);
   }
   return max_sum;
}

class Solution {
   public:
       int solution(vector<int>& nums) {
           if (nums.size() == 0) return 0;
           int max_sum = nums[0];
           int current_sum = nums[0];
           for (int i = 1; i < nums.size(); i++) {
               current_sum = max(nums[i], current_sum + nums[i]);
               max_sum = max(max_sum, current_sum);
           }
           return max_sum;
       }
   };

class Solution {
   public int solution(int[] nums) {
       if (nums.length == 0) return 0;
       int max_sum = nums[0];
       int current_sum = nums[0];
       for (int i = 1; i < nums.length; i++) {
           current_sum = Math.max(nums[i], current_sum + nums[i]);
           max_sum = Math.max(max_sum, current_sum);
       }
       return max_sum;
   }
}

def solution(nums):
   if not nums:
       return 0
   max_sum = nums[0]
   current_sum = nums[0]
   for i in range(1, len(nums)):
       current_sum = max(nums[i], current_sum + nums[i])
       max_sum = max(max_sum, current_sum)
   return max_sum

function solution(nums) {
   if (nums.length === 0) return 0;
   let max_sum = nums[0];
   let current_sum = nums[0];
   for (let i = 1; i < nums.length; i++) {
       current_sum = Math.max(nums[i], current_sum + nums[i]);
       max_sum = Math.max(max_sum, current_sum);
   }
   return max_sum;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Max Subarray Sum Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Max Subarray Sum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor