Maximum Subarray
Problem link: https://leetcode.com/problems/maximum-subarray/
Problem Statement
Given an integer array nums, find the subarray with the largest sum, and return its sum.
A subarray is a contiguous part of an array.
Input
An integer array nums.
Output
The maximum possible sum of a contiguous subarray.
Example
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.
Explanation
The max sum is found by picking the sequence 4, -1, 2, 1. Even though -1 is negative, the overall sum increases later.
Brute Force
Intuition
Check every possible subarray sum by using two nested loops to define the start and end of the subarray, and a third loop to calculate the sum.
Approach
- Initialize maxi to a very small number.
- Use a loop i from 0 to n-1 (start of subarray).
- Use a nested loop j from i to n-1 (end of subarray).
- Calculate sum of elements from i to j.
- Update maxi = max(maxi, sum).
Dry Run
nums = [-2, 1] i=0, j=0: sum=-2 i=0, j=1: sum=-1 i=1, j=1: sum=1 Max is 1.
Code (Java)
class Solution {
public int maxSubArray(int[] nums) {
int maxi = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
maxi = Math.max(maxi, sum);
}
}
return maxi;
}
}
Complexity Analysis
We use two nested loops to traverse the array.
Optimal Solution
Intuition
Kadane's Algorithm: As we traverse, we keep adding elements to a running sum. If the running sum becomes negative, it's better to 'discard' it and start fresh from the current element, because a negative prefix will only decrease our future potential sum.
Approach
- Initialize sum = 0 and maxi = nums[0].
- Iterate through the array.
- Add current element to sum.
- Update maxi = max(maxi, sum).
- If sum < 0, reset sum to 0.
- Return maxi.
Dry Run
nums = [-2, 1, -3, 4]
- sum = -2, maxi = -2 -> sum < 0, reset sum = 0
- sum = 1, maxi = 1
- sum = 1 + (-3) = -2, maxi = 1 -> sum < 0, reset sum = 0
- sum = 4, maxi = 4 Final Answer: 4
Code (Java)
class Solution {
public int maxSubArray(int[] nums) {
int maxi = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum > maxi) maxi = sum;
if (sum < 0) sum = 0;
}
return maxi;
}
}
Complexity Analysis
We traverse the array exactly once.
Quick Revision (Brute Force)
- Check all subarrays
- O(N^2) or O(N^3) time
Quick Revision (Optimal)
- Kadane's Algorithm
- Keep adding to sum
- If sum < 0, reset to 0
- Always track global maxi
- O(N) time