Practice/Uber/Leetcode 53. Maximum Subarray

Leetcode 53. Maximum Subarray

CodingMust

Problem

Given an integer array, find the contiguous subarray that has the largest sum and return that sum value.

A subarray is a contiguous portion of the array. For example, in the array [1, 2, 3, 4], some subarrays include [1, 2], [2, 3, 4], and [1, 2, 3, 4], but [1, 3] is not a valid subarray because the elements are not contiguous.

Requirements

1. Return the sum of the contiguous subarray with the maximum sum
2. Handle arrays containing negative numbers, positive numbers, or a mix of both
3. If all numbers are negative, return the largest (least negative) number
4. Implement an efficient solution that processes the array in a single pass

Constraints

• 1 ≤ nums.length ≤ 105
• -104 ≤ nums[i] ≤ 104
• Target time complexity: O(n)
• Target space complexity: O(1)

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 of 6

Example 2:

Input: nums = [1] Output: 1 Explanation: With a single element, that element is the answer

Example 3:

Input: nums = [5, 4, -1, 7, 8] Output: 23 Explanation: The entire array [5, 4, -1, 7, 8] has the largest sum of 23

Example 4:

Input: nums = [-3, -2, -5, -1] Output: -1 Explanation: When all numbers are negative, we choose the largest value