Given an integer array nums, find the subarray with the largest sum, and return its sum.
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 6.
Example 2:
Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
The Maximum Subarray problem asks you to find a contiguous subarray within an array that has the largest possible sum. A brute-force approach would check all subarrays, but that results in O(n^2) or worse time complexity.
The most efficient solution uses Kadane’s Algorithm, a dynamic programming technique. The key idea is to iterate through the array while maintaining the current running sum. If the running sum becomes negative, it is better to start a new subarray from the next element. At every step, update the global maximum sum encountered so far. This allows the algorithm to solve the problem in linear time.
Another approach uses Divide and Conquer. The array is split into two halves, and the solution considers the best subarray in the left half, the right half, and one that crosses the midpoint. Although conceptually interesting, it is typically less efficient than Kadane’s algorithm for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Kadane's Algorithm (Dynamic Programming) | O(n) | O(1) |
| Divide and Conquer | O(n log n) | O(log n) |
CS Dojo
This approach uses Kadane's Algorithm, which is an efficient way to find the maximum subarray sum in linear time.
We iterate through the array, keeping track of the maximum sum of the subarray ending at the current position and the overall maximum sum found so far.
The algorithm maintains two variables: current_max, which is the maximum sum of the subarray that ends at the current index, and global_max, which is the maximum sum found so far.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), because we are using a constant amount of extra space.
1#include <stdio.h>
2#include <limits.h>
3
4int maxSubArray(int* nums, int numsSize) {
5 int current_max =
This C code implements Kadane's Algorithm. We initialize current_max and global_max to the first element of the array, then iterate through the array, updating these values based on the logic of Kadane's algorithm.
This approach splits the array into two halves and finds the maximum subarray sum for each half recursively. It also considers the possibility of the maximum subarray crossing the midpoint.
To find the maximum crossing subarray, we begin at the midpoint and expand outward to the left and right, keeping track of the maximum sum.
This approach effectively divides the problem into smaller subproblems and conquers each independently, then combines their results.
Time Complexity: O(n log n)
Space Complexity: O(log n) for the recursion stack
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Maximum Subarray is a very common interview question at FAANG and other top tech companies. It tests understanding of dynamic programming, greedy thinking, and the ability to optimize brute-force solutions.
The optimal approach is Kadane’s Algorithm, a dynamic programming technique that processes the array in a single pass. It keeps track of the current subarray sum and the global maximum sum, achieving O(n) time complexity with constant space.
Kadane’s Algorithm works because any negative running sum will only reduce the total of future subarrays. By resetting the running sum when it becomes negative, the algorithm always keeps the most beneficial starting point for the maximum sum.
The problem mainly relies on array traversal and does not require complex data structures. The optimized solution only tracks running sums using variables while iterating through the array.
This C implementation uses divide and conquer to find the maximum contiguous subarray sum. It divides the array into two halves, recursively finds the maximum subarray sum in each half, and also finds the maximum crossing sum that can be obtained by including elements from both halves.