Find the Maximum-Sum Contiguous Subarray

Problem Statement

You are given an array of integers nums. Your task is to find the contiguous non-empty subarray that has the largest sum and return that sum.

A subarray is a contiguous part of an array. The solution must operate in O(n) time complexity and use O(1) auxiliary memory. Pay special attention to edge cases such as arrays containing only negative numbers, and ensure calculations do not overflow standard 32-bit integer limits where applicable.

Function Signature

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

Input & Output Format

• Input: A list of integers nums where 1 <= len(nums) <= 10^5.
• Output: An integer representing the maximum possible sum of any contiguous, non-empty subarray.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• The accumulated sum can exceed the 32-bit signed integer range, so use 64-bit integer types if working in languages like C++ or Java (long long / long).

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, -2, -8, -1, -4]
Output: -1
Explanation: Because the subarray must be non-empty, the maximum sum is -1, corresponding to the single-element subarray [-1].

Edge Cases

• Arrays containing only a single element (the result must be that single element).
• Arrays containing exclusively negative values (the result is the maximum single negative number, not 0).
• Arrays with large values where intermediate sums exceed 2^31 - 1.