Help the world stop coronavirus! Stay home!

Prev Next

Java / Programs

Write a Java program to find the subArray in an Integer Array that has maximum Sum of the elements.

public class FindSubArrayWithMaxSum {

	public static void main(String[] args) {

		// Creating a bucket of integer array with various test values for unit testing
		int[][] myArr = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, -11 }, { 1, 2, 3, 0, 4, 3, -1, 3, 5, 5, 6, 6, -2, 50 },
				{ -3, 0, -1 }, { 0, -1 }, {}, { -2 }, { 2 }, { 0 }, { 1, 2, 3, -1, 1, 2, 3, 4, 0, -1, 1, 1 } };

		// For each of the above data set find the sumArray with Maximum sum
		IntStream.range(0, myArr.length).mapToObj(i -> myArr[i]).parallel()
				.forEach(FindSubArrayWithMaxSum::findMaxSumSubArray);
	}

	static void findMaxSumSubArray(int[] myArr) {
		if (myArr.length == 0)
			return;

		int positionI = 0, positionJ = 0;
		int tempPositionI = 0, tempPositionJ = 0;
		int maxSum, tempSum;

		maxSum = tempSum = myArr[0];

		for (int i = 1; i < myArr.length; i++) {
			if (tempPositionI >= i || tempSum < 0) {
				tempPositionI = tempPositionJ = i;
				tempSum = myArr[i];
				continue;
			}
			if ((tempSum + myArr[i]) >= tempSum) {
				tempSum += myArr[i];
				tempPositionJ = i;
			} else if (i + 1 < myArr.length) {
				positionI = tempPositionI;
				positionJ = tempPositionJ;
				maxSum = tempSum;
				tempPositionI = i + 1;
			}
		}

		if (tempSum > maxSum) {
			positionI = tempPositionI;
			positionJ = tempPositionJ;
			maxSum = tempSum;
		}

		System.out.println(
				Arrays.toString(myArr) + " >> Start Position: " + positionI + " End Position: " + positionJ + ", Sum: " + maxSum);
	}

}

❤Cash Back At Stores you Love !!!❤

Earn your $10 reward when you make your first purchase through Ebates by signing up with clicking below button.

Ebates Coupons and Cash Back

More Related questions...

Show more question and Answers...

JVM

Comments & Discussions