Welcome Message

Hi, welcome to my website. This is a place where you can get all the questions, puzzles, algorithms asked in interviews and their solutions. Feel free to contact me if you have any queries / suggestions and please leave your valuable comments.. Thanks for visiting -Pragya.

Showing posts with label Subarray having maximum sum. Show all posts
Showing posts with label Subarray having maximum sum. Show all posts

December 29, 2009

Program to find Subarray having maximum sum in a given integer array

public static void findSubarray(int[] arr){
int len = arr.length;
int largest = 0;
int lowerBound = 0;
int upperBound = 0;
for(int i = 0 ; i < len ; i++){

int sum = arr[i];
for(int j = i+1 ; j < len ; j++){
sum += arr[j];
if(sum > largest){
largest = sum;
lowerBound = i;
upperBound = j;
}
}
}
System.out.println("Largest sum is : "+largest );
System.out.println("Largest subarray is between "+arr[lowerBound]+ " and "+arr[upperBound]);

}