Maximum Subarray
MedPrompt
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] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves generating every possible contiguous subarray, calculating the sum of each, and keeping track of the maximum sum found. This method guarantees finding the correct answer by exhaustively checking all possibilities.
Algorithm
- Initialize a variable
maxSumto the smallest possible integer value. - Use a nested loop structure. The outer loop, with index
i, iterates from the start to the end of the array, fixing the starting element of a subarray. - The inner loop, with index
j, iterates fromito the end of the array, fixing the ending element of a subarray. - For each subarray defined by
iandj, calculate its sum. A third loop can be used, or more efficiently, acurrentSumvariable can be updated within the second loop. - Compare the
currentSumof each subarray withmaxSum. IfcurrentSumis greater, updatemaxSum. - After iterating through all possible subarrays,
maxSumwill hold the maximum subarray sum.
Walkthrough
This method considers every possible subarray. We can define a subarray by its start and end indices. We use two nested loops to iterate through all possible start and end points. The outer loop selects the starting index i, and the inner loop selects the ending index j.
For each pair of (i, j), we calculate the sum of the elements in nums from index i to j. We maintain a global variable, maxSum, initialized to a very small number (like Integer.MIN_VALUE). As we calculate the sum of each subarray, we compare it with maxSum and update maxSum if the current subarray's sum is larger.
An optimization to the naive three-loop approach is to calculate the sum iteratively in the second loop. As j increments, we just add nums[j] to the sum of the subarray nums[i...j-1]. This reduces the complexity from O(n³) to O(n²).
class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int maxSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { // Add the current element to the subarray sum currentSum += nums[j]; // Update maxSum if the current subarray sum is greater if (currentSum > maxSum) { maxSum = currentSum; } } } return maxSum; }}Complexity
Time
O(n^2)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Correctness is easy to verify.
Cons
Very inefficient for large arrays.
Will likely result in a 'Time Limit Exceeded' (TLE) error on most online coding platforms for the given constraints.
Solutions
Solution
public class Solution { public int MaxSubArray(int[] nums) { int ans = nums[0], f = nums[0]; for (int i = 1; i < nums.Length; ++i) { f = Math.Max(f, 0) + nums[i]; ans = Math.Max(ans, f); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.