Kadane's Algorithm
Solving Maximum Sum Subarray Problem in O(n) time as opposed to O(n * n) brute force solution

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Maximum subarray problems arise in many fields, such as genomic sequence analysis and computer vision.
Genomic sequence analysis employs maximum subarray algorithms to identify important biological segments of protein sequences. These problems include conserved segments, GCrich regions, tandem repeats, lowcomplexity filter, DNA binding domains, and regions of high charge.
In computer vision, maximumsubarray algorithms are used on bitmap images to detect the brightest area in an image.
In computer science, the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given onedimensional array A[1...n] of numbers.
Some variations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero. Each number in the input array A could be positive, negative, or zero.
For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6.
Some properties of this problem are:
 If the array contains all nonnegative numbers, then the problem is trivial; a maximum subarray is the entire array.
 If the array contains all nonpositive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted).
 Several different subarrays may have the same maximum sum.
Variation # 1:
Problem Statement:
Given an integer array nums, find the contiguous subarray which has the largest sum and return its sum. Largest sum cannot be negative.
Example 1:
Input: nums = [2,1,3,4,1,2,1,5,4]
Output: 6
Explanation: [4,1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1, 2, 3]
Output: 0
Solution:
Kadane's Algorithm becomes very easy to understand and intuitive, when you are able to make one important observation:
While computing maximum sum subarray, a subarray has any purpose to it next contiguous subarray only
when the sum of the subarray is nonnegative.
What this means is if the given array is [1, 2, 3, 4], the subarray [1, 2] cannot contribute to maximize sum to the next subarray [3,4] since the sum of the subarray [1, 2] is 3. So adding subarray [1. 2] to its adjacent subarray [3, 4] will only drag the sum of the subarray [3, 4] down. So at any point of time we get a subarray with sum less than 0, we would know for sure that this subarray combined with adjacent right subarray can never give greater sum than the adjacent subarray alone. [3, 4] alone gives sum 7. But if we add [1, 2] to [3, 4] the sum becomes 4. So the maximum sum subarray can never be [1, 2, 3, 4]. It has to be [3, 4]. Look at the below code to see how this observation is used to come up with an efficient algorithm called Kadane's Algorithm.
Code:
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
int globalMax = 0; // global max can be 0 at the minimum
int localMax = 0;
for (int i = 0; i < nums.length; i++) {
localMax = Math.max(localMax + nums[i], 0); // localMax will contribute
// to finding subarray with greater sum
// as long as localMax is nonnegative.
// Because, if the localMax is negative it
// will bring the future sum down.
// So, anytime localMax becomes negative, we
// make it zero to nullify the negative effect.
globalMax = Math.max(globalMax, localMax);
}
return globalMax;
}
}
Variation #2:
Problem Statement:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [2,1,3,4,1,2,1,5,4]
Output: 6
Explanation: [4,1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [0]
Output: 0
Example 4:
Input: nums = [1]
Output: 1
Example 5:
Input: nums = [2, 3, 5]
Output: 2
Solution:
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
int globalMax = Integer.MIN_VALUE;
int localMax = 0;
for (int i = 0; i < nums.length; i++) {
globalMax = Math.max(globalMax, localMax + nums[i]);
localMax = Math.max(localMax + nums[i], 0); // localMax will contribute
// to finding subarray with greater sum
// as long as localMax is nonnegative.
// Because, if the localMax is negative it
// will bring the future sum down.
// So, anytime localMax becomes negative, we
// make it zero to nullify the negative effect.
}
return globalMax;
}
}
Must Read Chapters:
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn