## 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: The subarray [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`). Here is how `maxEndingHere` is calculated:

• Initialize `maxEndingHere` to `nums[0]`

• Iterate through the array (`1..n`). For every iteration:

• If `maxEndingHere + nums[i] < nums[i]`, that means the previous max was negative and therefore we reset `maxEndingHere` to `nums[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 than `maxSoFar`. If yes, then we update the value of `maxSoFar`.

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``````