MediumSliding WindowAI interview only
Maximum Subarray
Asked atgoogleamazonmetamicrosoftbloomberglinkedinapple
01 · Problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
A subarray is a contiguous non-empty sequence of elements within an array.
02 · Examples
Example 01
Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6
The subarray [4,-1,2,1] has the largest sum 6.
Example 02
Input
nums = [1]
Output
1
The subarray [1] has the largest sum 1.
Example 03
Input
nums = [5,4,-1,7,8]
Output
23
The subarray [5,4,-1,7,8] has the largest sum 23.
03 · Constraints
- 011 <= nums.length <= 105
- 02-104 <= nums[i] <= 104
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.