This tutorial covers the solution for the Maximum Subarray Problem. We will cover the complete code solution for the Maximum Subarray Problem in Java programming language.
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.
For Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation:
The Subarray [4, -1, 2, 1] has the largest sum = 6 out of all the possible subarrays in the given array.
Logic:
Usually, the standard approach to solve this types of problem is the Divide and Conquer strategy. But it is very tough for the beginners to implement this programming paradigm in code.
So to solve this issue, we have introduced a new logic to implement this problem so that even beginners who are new to this can get along with this. Lets dive into the logic without any further delay.
To solve this problem, we need to handle two specific cases:
Case 1: All the elements are Negative numbers.
If all the elements in the array are negative numbers, then, the sum of the subarray will be maximum when it contains only the least magnitude number (the smallest negative number) as adding any other element, will just be adding more negative quantity to it thereby making it less.
This case is handled by the code written below:
int l = nums.length;
int i=0, s=0, max=nums[0];
int[] b = new int[l];
while(i != l)
{
b[i]=nums[i];
i++;
}
// if(l==1)
// return nums[0];
Arrays.sort(b);
/* if the last element (maximum value) in the
sorted array is negative, then all the elements
are negative */
if(b[l-1] <= 0)
return b[l-1];
Case 2: At least one non-negative number in Array:
-
For such cases, we can initialize the max value to be returned to the first element of the original array, here we will be dealing with the original i.e. the unsorted array as we need to maintain the original order of the elements as the problem involves the concept of subarrays.
-
Now make use of a loop till the last element of the array and keep adding the current element onto the sum value.
-
If the sum value is less than 0, then initialise the sum to 0 and move ahead in the array as adding this element will only decrement the sum, so we need to ignore this element.
-
If this value is greater than the max value, then update the max value to this sum and keep repeating this task.
-
By doing this, the sum variable will contain the current max value of the subarray under consideration and the max variable will contain the overall maximum sum of the subarray till the current element.
-
This max variable will store the value to be returned as the final answer of our code.
The code to handle all such cases can be seen below:
i = 0;
while(i!=l)
{
s += nums[i];
if(s < 0)
{
s=0;
}
else if(s>max)
max=s;
System.out.println(max);
i++;
}
System.out.println(max);
return max;
We know that this might not be completely clear for you at the first go, but we are sure that once you start writing this code on your own, you will surely develop a better understanding of the mentioned logic.
Complete Solution in Java:
So let's look at the final code that solves the problem in hand.
class Solution {
public int maxSubArray(int[] nums) {
int l=nums.length;
int i=0,s=0,max=nums[0];
int[] b = new int[l];
while(i!=l)
{
b[i]=nums[i];
i++;
}
// if(l==1)
// return nums[0];
Arrays.sort(b);
if(b[l-1]<=0)
return b[l-1];
i=0;
while(i!=l)
{
s+=nums[i];
if(s<0)
{
s=0;
}
else if(s>max)
max=s;
System.out.println(max);
i++;
}
System.out.println(max);
return max;
}
}
Incase of any confusion regarding the above solution, you can reach out to us over the email or can mention the query in the comments section down below.
Will answer them in the best possible way.
Thanks for reading!
We hope that this post might have helped you to get your logic even stronger and implement the code as well.
Happy Quarantine : )
You may also like:
