Maximum Subarray Sum
Updated
Problem statement
In this problem, a subarray of nums is a run of one or more values that sit next to each other. An empty run does not count.
Every subarray has a total, found by adding up its values. Out of all subarrays of nums, the answer is the biggest such total.
Function
maxSubarraySum(nums: int[]) → intExamples
Example 1
nums = [-2,7,-8,3,3,-1,5]return = 10A stretch that starts at 7 or earlier and still reaches the 3s must cross -8. Since 7 - 8 = -1, starting that early only lowers the total, and 7 on its own gives just 7. Starting at the first 3 and running to the end gives 3 + 3 - 1 + 5 = 10. Leaving out the -1 would also cut off the 5 after it, so no stretch beats 10.
Example 2
nums = [-6,-11,-3,-9]return = -3No number here is above zero, so adding another number to a subarray always lowers its sum. Taking -3 by itself loses the least, which makes -3 the result.
Example 3
nums = [3,-8,2,2,-1,4]return = 7A stretch that starts at the opening 3 and goes further must also take -8, a net loss of 5, and 3 alone is only 3, so the best stretch starts after them. From the first 2 to the end the values add up to 2 + 2 - 1 + 4 = 7, and dropping the -1 would also drop the 4, which leaves 7 as the best total.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4
More Capital One interview questions
- Count Records Present in A but Not BPHONE SCREEN · Seen Oct 2026
- LRU CachePHONE SCREEN · ONSITE INTERVIEW · Seen May 2026
- Ten-Pin Bowling Frame ScoresPHONE SCREEN · Seen Nov 2023
- Min StackPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2023
- Invert a Binary TreePHONE SCREEN · Seen Dec 2020
- Count How Often a Word Appears in a ParagraphPHONE SCREEN
- In-Memory File System With Directory SizesPHONE SCREEN · ONSITE INTERVIEW
- Pick the K Nearest Grid Points to (0, 0)PHONE SCREEN · ONSITE INTERVIEW
- The Nth Number in the Fibonacci SequencePHONE SCREEN · ONSITE INTERVIEW
- Digit-Coded Card ValidationONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Maximum Subarray Sum with Equal EndpointsGoogle · ONSITE INTERVIEWGoogle interview questions
- Largest All-One Square Area and CountNVIDIA · PHONE SCREENNVIDIA interview questions
- Maximum Apples from Two Disjoint Fixed-Length SegmentsMarshall Wace · OAMarshall Wace interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Maximize CollaborationTikTok · OATikTok interview questions
- Maximum Sum RectangleDeloitte · OADeloitte interview questions
- Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
- Fewest Coins CombinationBloomberg LP · PHONE SCREENBloomberg LP interview questions
Capital One interview experiences
- Capital One Experienced Engineer Power Day and OA: 6 Experiences
- Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
- Capital One TDP Agentic Round (AI Coding): 7 Experiences
- Capital One SWE Power Day, Level Not Reported: 6 Experiences
- Capital One TIP Intern OA and Power Day: 13 Experiences
- Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)