Maximum Subarray
Problem Description
Question
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]
0
-2
1
1
2
-3
3
4
4
-1
5
2
6
1
7
-5
8
4
Output:6
6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input:nums=[1]
0
1
Output:1
1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input:nums=[5,4,-1,7,8]
0
5
1
4
2
-1
3
7
4
8
Output:23
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.
Solve it on LeetCode
Approaches
1. Brute Force
The brute force approach involves checking every possible subarray and computing the sum of each one. This method is straightforward but inefficient for larger arrays due to its high time complexity.
Intuition:
- Iterate through each element of the array, treating it as the start of a subarray.
- For each start point, explore all possible end points and compute the sum for each subarray.
- Track the maximum sum encountered.
Code:
Complexity Analysis
- Time Complexity: O(n^2) - We have a nested loop where for each element, we compute sums up to the end of the array.
- Space Complexity: O(1) - We only use a constant amount of extra space for variables.
2. Kadane's Algorithm
Kadane's Algorithm provides an efficient way of finding the maximum subarray sum in linear time.
Intuition:
- Traverse the array, maintaining a running maximum sum of contiguous elements (
currentSum). - If
currentSumdrops below zero, reset it to the current element, as a negativecurrentSumwould decrease the sum of any subarray including it. - Track a global maximum (
maxSum) across all encounteredcurrentSumvalues.
Code:
Complexity Analysis
- Time Complexity: O(n) - We traverse the array once, updating the running sum and maximum.
- Space Complexity: O(1) - We use a constant amount of extra space for variables (
currentSumandmaxSum).