Approach Summary
Kadane's: at each position, current max = max(num, prevMax + num). Global max tracked throughout.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (All Subarrays) | O(n²) | O(1) | Iterate over all possible starting indices i and ending indices j to sum subarrays. |
| 2 Approach 2: Kadane's Algorithm (Optimal) | O(n) | O(1) | Track running subarray sum and reset to zero whenever it drops negative. |
Approach 1: Brute Force (All Subarrays)
Fix a start position i from 0 to n - 1. Then loop j from i to n - 1, keeping a running sum `currentSum += nums[j]`. Update `maxSum = max(maxSum, currentSum)`. While easy to conceptualize, generating ~n²/2 subarrays takes several seconds for n = 10⁵, leading to TLE.
Approach 1: Brute Force (All Subarrays) Implementation
Approach 1: Brute Force (All Subarrays)
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int curr = 0;
for (int j = i; j < nums.length; j++) {
curr += nums[j];
maxSum = Math.max(maxSum, curr);
}
}
return maxSum;
}
}class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int n = nums.size();
for (int i = 0; i < n; i++) {
int curr = 0;
for (int j = i; j < n; j++) {
curr += nums[j];
maxSum = max(maxSum, curr);
}
}
return maxSum;
}
};def max_sub_array(nums: list[int]) -> int:
max_sum = float('-inf')
n = len(nums)
for i in range(n):
curr = 0
for j in range(i, n):
curr += nums[j]
max_sum = max(max_sum, curr)
return int(max_sum)function maxSubArray(nums) {
let maxSum = -Infinity;
const n = nums.length;
for (let i = 0; i < n; i++) {
let curr = 0;
for (let j = i; j < n; j++) {
curr += nums[j];
maxSum = Math.max(maxSum, curr);
}
}
return maxSum;
}Approach 2: Kadane's Algorithm (Optimal)
At each step i, we add nums[i] to `currSum` and compare it with `maxSum`. If `currSum` becomes negative, any contiguous sequence starting with or including this prefix will have a lower sum than starting fresh from the next element. Hence, we reset `currSum = 0`. By updating `maxSum` before resetting, we correctly handle arrays with all negative numbers as well.
Approach 2: Kadane's Algorithm (Optimal) Implementation
Approach 2: Kadane's Algorithm (Optimal)
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int currSum = 0;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
currSum += nums[i];
maxSum = Math.max(maxSum, currSum);
if (currSum < 0) {
currSum = 0;
}
}
return maxSum;
}
}class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int currSum = 0;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++) {
currSum += nums[i];
maxSum = max(maxSum, currSum);
if (currSum < 0) {
currSum = 0;
}
}
return maxSum;
}
};def max_sub_array(nums: list[int]) -> int:
curr_sum = 0
max_sum = float('-inf')
for num in nums:
curr_sum += num
max_sum = max(max_sum, curr_sum)
if curr_sum < 0:
curr_sum = 0
return int(max_sum)function maxSubArray(nums) {
let currSum = 0;
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
currSum += nums[i];
maxSum = Math.max(maxSum, currSum);
if (currSum < 0) {
currSum = 0;
}
}
return maxSum;
}Edge Cases to Watch
- Array containing all negative numbers (e.g. [-3, -2, -5]) — must return the single largest element (-2)
- Array with a single element
- Alternating large positive and negative numbers
- All positive numbers (sum of the entire array)
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
How to Recognize This Pattern
- Maximum sum subarray
- Kadane's algorithm
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)