Arrays and Hashing One pass with running state
71. Maximum Subarray
You are given an array of integers nums. Return the largest sum that a subarray of nums can have.
A subarray is a contiguous part of nums that holds at least one element. Each single element is a
subarray, and so is the whole array. You only return the sum, not the subarray itself.
Example 1
Input: nums = [3, -4, 5, -1, 2, -6, 4]
6Explanation: The best subarray is [5, -1, 2]. Taking the −1 pays off, because the 2 after it more than makes up
for it. The whole array adds up to only 3.
Example 2
Input: nums = [1000000000, 1000000000, -5, 1000000000]
2999999995Explanation: The whole array is the best subarray. Its sum, 2,999,999,995, is more than 2,147,483,647, the largest value a 32-bit integer can hold.
Example 3
Input: nums = [-8, -3, -6]
-3Explanation: Every element is negative, and a subarray cannot be empty. The best choice is the single element −3.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.