• 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.



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:
  1. If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
  2. 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).
  3. 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:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.








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:





This is a Premium Content.
Please subscribe to Algorithms course to access the solution.




Python Solution:





This is a Premium Content.
Please subscribe to Algorithms course to access the solution.





Must Read Chapters:




The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave