Maximum Subarray Sum

Maximum Subarray Sum Problem

The Maximum Subarray Sum problem asks you to find a contiguous subarray within a one-dimensional numeric array that has the largest possible sum, and return that sum. This classic problem appears in PayPal interviews tagged with Array, Dynamic Programming (Kadane's algorithm O(n)), and Divide and Conquer (O(n log n)).[1][9]

Full 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; it must handle both positive and negative numbers, and the result could be negative if all numbers are negative.[9][1]

Input/Output Examples

| Input | Output | Explanation | |------------------------|--------|--------------------------------------------------| | [-2,1,-3,4,-1,2,1] | 6 | Subarray [4,-1,2,1] sums to 6 | | [2,3,-8,7,-1,2,3] | 11 | Subarray [7,-1,2,3] sums to 11 | | [-2,-4] | -2 | Single element [-2] (largest among negatives) | | [5,4,1,7,8] | 25 | Entire array sums to 25 | | [-1] | -1 | Single negative element | | [] | N/A | Empty array (typically invalid) | [1][9][2]

Constraints

• 1 <= nums.length <= 10^5 (common for efficient solutions)[9]
• -10^4 <= nums[i] <= 10^4 (handles negatives and overflow in sums up to ~10^9)[9]
• Array is non-empty in standard formulations, but edge cases test single elements or all negatives[1]