Maximum Contiguous Subarray Sum
Maximum Contiguous Subarray Sum problem statement
Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Maximum Contiguous Subarray Sum solution in Java
This problem can be solved using Kadane’s algorithm in O(n)
time complexity.
The algorithm iterates over all the elements of the array (nums
) and computes the maximum sum ending at every index (maxEndingHere
). The idea for computing maxEndingHere
is simple:
If
maxEndingHere + nums[i] < nums[i]
that means, the previous max was negative and therefore we resetmaxEndingHere
tonums[i]
.Otherwise, we set
maxEndingHere = maxEndingHere + nums[i]
We also keep a variable
maxSoFar
which indicates the maximum sum found so far. And, with every iteration, we check if the current max (maxEndingHere
) is greater thanmaxSoFar
. If yes, then we update the value ofmaxSoFar
.
Here is the complete solution:
import java.util.Scanner;
class MaximumSubarray {
private static int findMaxSubarraySum(int[] nums) {
int n = nums.length;
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for(int i = 1; i < n; i++) {
if(maxEndingHere + nums[i] < nums[i]) {
maxEndingHere = nums[i];
} else {
maxEndingHere = maxEndingHere + nums[i];
}
if(maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
}
}
return maxSoFar;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = keyboard.nextInt();
}
System.out.println(findMaxSubarraySum(nums));
}
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
6
Maximum Contiguous Subarray with Indices
It’s also possible to find out the start and end indices of the maximum contiguous subarray. Here is a modification of the above program which does that and prints the subarray -
import java.util.Scanner;
class MaximumSubarray {
private static int[] findMaxSubarrayIndices(int[] nums) {
int n = nums.length;
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
int currentStart = 0, maxStart = 0, maxEnd = 0;
for(int i = 1; i < n; i++) {
if(maxEndingHere + nums[i] < nums[i]) {
maxEndingHere = nums[i];
currentStart = i;
} else {
maxEndingHere = maxEndingHere + nums[i];
}
if(maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
maxStart = currentStart;
maxEnd = i;
}
}
return new int[]{maxStart, maxEnd};
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = keyboard.nextInt();
}
int[] indices = findMaxSubarrayIndices(nums);
int sum = 0;
System.out.print("Max contiguous subarray: ");
for(int i = indices[0]; i <= indices[1]; i++) {
System.out.print(nums[i] + " ");
sum += nums[i];
}
System.out.println();
System.out.println("Max contiguous subarray sum: " + sum);
}
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
Max contiguous subarray: 4 -1 2 1
Max contiguous subarray sum: 6