Thursday, December 1, 2016

Find Continious SubArray With Maximum Sum Problem

public class MaxSumSubArray {

public static void main(String[] args) {
// sample input elements
int[] intArr = { 0, -1, 2, -1, 3, -1, 2, 0, 0, 0 };
findMaxSubArray(intArr);
}

public static void findMaxSubArray(int[] inputArray) {

int maxStartIndex = 0;
int maxEndIndex = 0;
// intializing maxSum to least possible integer
int maxSum = Integer.MIN_VALUE;

int cumulativeSum = 0;
int maxStartIndexTilNow = 0;

for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {

int eachArrayItem = inputArray[currentIndex];

cumulativeSum += eachArrayItem;

if (cumulativeSum > maxSum) {
maxSum = cumulativeSum;
// startindex is the next index of last element till which
// cumulative sum < 0
maxStartIndex = maxStartIndexTilNow;
// assign end index with current index for every increase in
// cumulative sum
maxEndIndex = currentIndex;
} else if (cumulativeSum < 0) {
maxStartIndexTilNow = currentIndex + 1;
cumulativeSum = 0;
}
}

System.out.println("Maximum sum         : " + maxSum);
System.out.print("Continious array with Maximum Sum is : {");

for (int i = maxStartIndex; i <= maxEndIndex; i++) {
if (i != maxEndIndex)
System.out.print(inputArray[i] + ",");
else
System.out.print(inputArray[i]);

}
System.out.print("}");

}

}

No comments:

Post a Comment