Print Largest Sum Contiguous Subarray

Given an array arr[] of length n, the task is to find the contiguous subarray within the array which has the largest sum. We can solve this problem in O(n) time complexity using Kadane's Algorithm.

arr [] = {-2, -3, 4, -1, -2, 1, 5, -3}, n = 8
Output: 7 (4, -1, -2, 1, 5)

Kadane's Algorithm simply takes two variables, maxSoFar and maxEndingHere; we initialize both variables with "0" and iterate the array elements one by one, in each iteration we add the current element value to maxEndingHere and compare it with maxSoFar, if maxEndingHere is greater than maxSoFar, maxSoFar will be maxEndingHere. If maxEndingHere becomes negative in any iteration we simply assign "0" to maxEndingHere.

package com.cd.array;

public class LargestSumContiguousSubarray {

	private static int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};

	private static int largestSum(int arr[], int n) {
		int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0;

		for (int i = 0; i < n; i++) {
			maxEndingHere += arr[i];
			if (maxEndingHere > maxSoFar)
				maxSoFar = maxEndingHere;
			if (maxEndingHere < 0)
				maxEndingHere = 0;
		}

		return maxSoFar;

	}

	public static void main(String[] args) {
		System.out.println(largestSum(arr, arr.length));

	}
}
Output: The output of above example will be something like this:


7



The above solution takes O(n) time and O(1) constant space, this solution is will return 0 if all the array elements are (-)ve, we can change this to consider array with all negative values by initializing maxSoFar and maxEndingHere with arr[0] instead of "0" and iterate array from index 1 as shown below.

package com.cd.array;

public class LargestSumContiguousSubarray {

	private static int arr[] = {-2, -3, -1, -2, -3};
	private static int arrA[] = {-2, -3, 4, -1, -2, 1, 5, -3};

	private static int largestSum(int arr[], int n) {
		int maxSoFar = arr[0], maxEndingHere = arr[0];

		for (int i = 1; i < n; i++) {
			maxEndingHere += arr[i];
			if (maxEndingHere > maxSoFar)
				maxSoFar = maxEndingHere;
			if (maxEndingHere < 0)
				maxEndingHere = 0;
		}

		return maxSoFar;

	}

	public static void main(String[] args) {
		System.out.println(largestSum(arr, arr.length));
		System.out.println(largestSum(arrA, arrA.length));

	}
}
Output: The output of above example will be something like this:


-1
7


Print Largest Sum Contiguous Subarray

In above two examples we have only printed the Largest Sum of Contiguous Subarray, here we will also print the actual Largest Sum Contiguous Subarray. All we need to do so is to maintain start and end of subArray as shown below.
package com.cd.array;

public class LargestSumContiguousSubarray {

	private static int arr[] = {-2, -3, -1, -2, -3};
	private static int arrA[] = {-2, -3, 4, -1, -2, 1, 5, -3};

	private static int largestSum(int arr[], int n) {
		int maxSoFar = arr[0], maxEndingHere = arr[0];
		int start = 0, end = 0, s = 0;

		for (int i = 1; i < n; i++) {
			maxEndingHere += arr[i];
			if (maxEndingHere > maxSoFar) {
				maxSoFar = maxEndingHere;
				end = i;
				start = s;
			}
			if (maxEndingHere < 0) {
				maxEndingHere = 0;
				s = i + 1;
			}
		}
		System.out.println("start: " + start + ", end: " + end);
		return maxSoFar;

	}

	public static void main(String[] args) {
		System.out.println(largestSum(arr, arr.length));
		System.out.println(largestSum(arrA, arrA.length));

	}
}
Output: The output of above example will be something like this:


start: 2, end: 2
-1
start: 2, end: 6
7