Program1: find sum of maxSubArray
public int maxSubArray(final int[] A) {
int largestSum = Integer.MIN_VALUE;
int tempSum = 0;
for(int i=0;i<A.length;i++) {
if(tempSum+A[i]<A[i]) {
tempSum = A[i];
}else {
tempSum = tempSum+A[i];
}
if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
if(largestSum<tempSum){
largestSum = tempSum;
}
}else {
tempSum=0;
}
}
return largestSum;
}
intput:{-2,1,-3,-4,-1,-2,-1,-7,-5,-4}
output: 1
innput:{-160,-20,-10}
output -10
input: -160,-20,-10,1,2
output: 3
Program2: find sum of maxSubArray with start and end index
public static void findMaxSumSubArray(int[] arr) {
int largestSum = Integer.MIN_VALUE;
int tempSum = 0;
int startIndex = 0;
int endIndex = 0;
int s = 0;
for(int i=0;i<arr.length;i++) {
if(tempSum+arr[i]<arr[i]) {
tempSum = arr[i];
}else {
tempSum = tempSum+arr[i];
}
if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
if(largestSum<tempSum){
endIndex = i;
startIndex = s;
largestSum = tempSum;
}
}else {
s = i+1;
tempSum=0;
}
}
System.out.println("index start::"+startIndex +" and end: "+endIndex);
System.out.println("sum::"+largestSum);
}
public int maxSubArray(final int[] A) {
int largestSum = Integer.MIN_VALUE;
int tempSum = 0;
for(int i=0;i<A.length;i++) {
if(tempSum+A[i]<A[i]) {
tempSum = A[i];
}else {
tempSum = tempSum+A[i];
}
if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
if(largestSum<tempSum){
largestSum = tempSum;
}
}else {
tempSum=0;
}
}
return largestSum;
}
intput:{-2,1,-3,-4,-1,-2,-1,-7,-5,-4}
output: 1
innput:{-160,-20,-10}
output -10
input: -160,-20,-10,1,2
output: 3
Program2: find sum of maxSubArray with start and end index
public static void findMaxSumSubArray(int[] arr) {
int largestSum = Integer.MIN_VALUE;
int tempSum = 0;
int startIndex = 0;
int endIndex = 0;
int s = 0;
for(int i=0;i<arr.length;i++) {
if(tempSum+arr[i]<arr[i]) {
tempSum = arr[i];
}else {
tempSum = tempSum+arr[i];
}
if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
if(largestSum<tempSum){
endIndex = i;
startIndex = s;
largestSum = tempSum;
}
}else {
s = i+1;
tempSum=0;
}
}
System.out.println("index start::"+startIndex +" and end: "+endIndex);
System.out.println("sum::"+largestSum);
}
No comments:
Post a Comment