Katkat
Back

Find the Maximum Sum of a Contiguous Subarray

OmnissaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to implement Kadane's algorithm to find the maximum sum of a contiguous subarray, specifically focusing on handling negative integers and maintaining optimal time and space complexity.

Problem Statement

Given an array of integers nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Function Signature

def max_subarray_sum(nums: list[int]) -> int:

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The result is guaranteed to fit in a 64-bit integer.

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 = [-5, -1, -8] Output: -1 Explanation: Since the subarray must be non-empty, the maximum sum is the largest single element.

Edge Cases

  • Arrays containing only negative numbers.
  • Arrays with a single element.
  • Arrays with very large positive or negative values (ensure 64-bit overflow handling).

Hints

Hint 1

Consider maintaining two variables: one for the maximum sum found so far globally, and one for the maximum sum ending at the current position.

Hint 2

If the current prefix sum becomes negative, it is always better to start a new subarray from the current element rather than continuing the existing one.

Hint 3

Initialize your tracking variables with the first element of the array rather than zero to correctly handle arrays consisting entirely of negative numbers.

Follow-up questions

  • How would you modify your solution to return the start and end indices of the subarray instead of just the sum?
  • If the array were circular (i.e., the end connects back to the start), how would you find the maximum subarray sum?
  • What is the time and space complexity of your solution, and can you prove that it is optimal?