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);
	}

}

It's right time to invest in Cryptocurrencies Dogecoin! Earn free bitcoins up to $250 now by signing up.

Earn bitcoins upto $250 (free), invest in other Cryptocurrencies when you signup with blockfi. Use the referral link: Signup now and earn!

Using BlockFi, don't just buy crypto - start earning on it. Open an interest account with up to 8.6% APY, trade currencies, or borrow money without selling your assets.


Join CoinBase! We'll both receive $10 in free Bitcoin when they buy or sell their first $100 on Coinbase! Available in India also. Use the referral Join coinbase!


Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.


Webull! Receive free stock by signing up using the link: Webull signup.

More Related questions...

Show more question and Answers...

JVM

Comments & Discussions