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



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 non-negative.
            // 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 non-negative.
            // 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

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