Kadane's Algorithm
Get started
জয় শ্রী রাম
🕉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, GC-rich regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge.
In computer vision, maximum-subarray 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 one-dimensional 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 non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
- If the array contains all non-positive 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 sub-arrays 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 non-negative.
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.
Java code:
Login to Access Content
Python Code:
Login to Access Content
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
Java Solution:
Login to Access Content
Python Solution:
Login to Access Content
