Search start and end index for max.

Question

public static void main(String[] args) { int arr[]= {0,-1,2,-3,5,9,-5,10}; int max_ending_here=0; int max_so_far=0; int start =0; int end=0; for(int i=0;i< arr.length;i++) { max_ending_here=max_ending_here+arr[i]; if(max_ending_here<0) { max_ending_here=0; } if(max_so_far<max_ending_here){ max_so_far=max_ending_here; } } System.out.println(max_so_far); } } 

this program generates the maximum sum of the subvariant array .. in this case its 19, using {5,9, -5,10} .. now I have to find the start and end index of this submatrix. How am i doing this?

Answer 1

Like this

 public static void main(String[] args) { int arr[]= {0,-1,2,-3,5,9,-5,10}; int max_ending_here=0; int max_so_far=0; int start =0; int end=0; for(int i=0;i< arr.length;i++){ max_ending_here=max_ending_here+arr[i]; if(max_ending_here<0) { start=i+1; //Every time it goes negative start from next index max_ending_here=0; } else end =i; //As long as its positive keep updating the end if(max_so_far<max_ending_here){ max_so_far=max_ending_here; } } System.out.println(max_so_far); } 

Ok, so there was a problem in the above solution, as indicated by Steve P. This is another solution that should work for everyone

 public static int[] compareSub(int arr[]){ int start=-1; int end=-1; int max=0; if(arr.length>0){ //Get that many array elements and compare all of them. //Then compare their max to the overall max start=0;end=0;max=arr[0]; for(int arrSize=1;arrSize<arr.length;arrSize++){ for(int i=0;i<arr.length-arrSize+1;i++){ int potentialMax=sumOfSub(arr,i,i+arrSize); if(potentialMax>max){ max=potentialMax; start=i; end=i+arrSize-1; } } } } return new int[]{start,end,max}; } public static int sumOfSub(int arr[],int start,int end){ int sum=0; for(int i=start;i<end;i++) sum+=arr[i]; return sum; } 

Answer 2

This is a program to solve this problem. I think the logic is the same for all languages, so I posted this answer.

 void findMaxSubArrayIndex(){ int n,*a; int start=0,end=0,curr_max=0,prev_max=0,start_o=0,i; scanf("%d",&n); a = (int*)malloc(sizeof(int)*n); for(i=0; i<n; i++) scanf("%d",a+i); prev_max = a[0]; for(i=0; i<n; i++){ curr_max += a[i]; if(curr_max < 0){ start = i+1; curr_max = 0; } else if(curr_max > prev_max){ end = i; start_o = start; prev_max = curr_max; } } printf("%d %d \n",start_o,end); } 

Answer 3

Here is the maxsubarray algorithm:

 public class MaxSubArray { public static void main(String[] args) { int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 }; //int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}; //int[] intArr={-6,-2,-3,-4,-1,-5,-5}; findMaxSubArray(intArr); } public static void findMaxSubArray(int[] inputArray){ int maxStartIndex=0; int maxEndIndex=0; int maxSum = Integer.MIN_VALUE; int cumulativeSum= 0; int maxStartIndexUntilNow=0; for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) { int eachArrayItem = inputArray[currentIndex]; cumulativeSum+=eachArrayItem; if(cumulativeSum>maxSum){ maxSum = cumulativeSum; maxStartIndex=maxStartIndexUntilNow; maxEndIndex = currentIndex; } if (cumulativeSum<0){ maxStartIndexUntilNow=currentIndex+1; cumulativeSum=0; } } System.out.println("Max sum : "+maxSum); System.out.println("Max start index : "+maxStartIndex); System.out.println("Max end index : "+maxEndIndex); } } 

Answer 4

Fixing the decision of Karl Saldanha:

  int max_ending_here = 0; int max_so_far = 0; int _start = 0; int start = 0; int end = -1; for(int i=0; i<array.length; i++) { max_ending_here = max_ending_here + array[i]; if (max_ending_here < 0) { max_ending_here = 0; _start = i+1; } if (max_ending_here > max_so_far) { max_so_far = max_ending_here; start = _start; end = i; } } 

Answer 5

The question is somewhat unclear, but I assume that the "sub-array" is half the arr object.

Lame way to do it like this

 public int sum(int[] arr){ int total = 0; for(int index : arr){ total += index; } return total; } public void foo(){ int arr[] = {0,-1,2,-3,5,9,-5,10}; int subArr1[] = new int[(arr.length/2)]; int subArr2[] = new int[(arr.length/2)]; for(int i = 0; i < arr.length/2; i++){ // Lazy hack, might want to double check this... subArr1[i] = arr[i]; subArr2[i] = arr[((arr.length -1) -i)]; } int sumArr1 = sum(subArr1); int sumArr2 = sum(subArr2); } 

I think this may not work if arr contains an odd number of elements.

If you want access to a higher level of support, convert primvate arrays to a List object

 List<Integer> list = Arrays.asList(arr); 

Thus, you have access to the functionality of the collection object.

Also, if you have the time, look at a higher order functional called shortening. You will need a library that supports functional programming. Guava or lambdaJ may have a reduction method. I know that apache-commons is missing one if you don't want to hack it together.

Answer 6

Here is the solution in python - the Kadan algorithm extended for printing start and end indices

 def max_subarray(array): max_so_far = max_ending_here = array[0] start_index = 0 end_index = 0 for i in range(1, len(array) -1): temp_start_index = temp_end_index = None if array[i] > (max_ending_here + array[i]): temp_start_index = temp_end_index = i max_ending_here = array[i] else: temp_end_index = i max_ending_here = max_ending_here + array[i] if max_so_far < max_ending_here: max_so_far = max_ending_here if temp_start_index != None: start_index = temp_start_index end_index = i print max_so_far, start_index, end_index if __name__ == "__main__": array = [-2, 1, -3, 4, -1, 2, 1, 8, -5, 4] max_subarray(array) 

Answer 7

 public static void maxSubArray(int []arr){ int sum=0,j=0; int temp[] = new int[arr.length]; for(int i=0;i<arr.length;i++,j++){ sum = sum + arr[i]; if(sum <= 0){ sum =0; temp[j] = -1; }else{ temp[j] = i; } } rollback(temp,arr); } public static void rollback(int [] temp , int[] arr){ int s =0,start=0 ; int maxTillNow = 0,count =0; String str1 = "",str2=""; System.out.println("============"); // find the continuos index for(int i=0;i<temp.length;i++){ if(temp[i] != -1){ s += arr[temp[i]]; if(s > maxTillNow){ if(count == 0){ str1 = "" + start; } count++; maxTillNow = s; str2 = " " + temp[i]; } }else{ s=0; count =0; if(i != temp.length-1) start = temp[i+1]; } } System.out.println("Max sum will be ==== >> " + maxTillNow); System.out.print("start from ---> "+str1 + " end to --- >> " +str2); } 

Answer 8

  public void MaxSubArray(int[] arr) { int MaxSoFar = 0; int CurrentMax = 0; int ActualStart=0,TempStart=0,End = 0; for(int i =0 ; i<arr.Length;i++) { CurrentMax += arr[i]; if(CurrentMax<0) { CurrentMax = 0; TempStart = i + 1; } if(MaxSoFar<CurrentMax) { MaxSoFar = CurrentMax; ActualStart = TempStart; End = i; } } Console.WriteLine(ActualStart.ToString()+End.ToString()); } 

Answer 9

The only thing I have to add (to the several solutions posted here) is to cover the case where all integers are negative, in which case the maximum auxiliary array will be just the maximum element. Pretty easy to do it. You just need to track the maximum element and the index index of the max element when it repeats. If the maximum element is negative, return it instead.

There is also an overflow case that is possibly being handled. I saw tests of algorithms that accept, not accounting. IE, suppose MAXINT was one of the elements, and you tried to add to it. I believe that some of the Codility tests (screening for coding testing) take this into account.

Answer 10

A solution to O (n) in C would be: -

 void maxsumindex(int arr[], int len) { int maxsum = INT_MIN, cur_sum = 0, start=0, end=0, max = INT_MIN, maxp = -1, flag = 0; for(int i=0;i<len;i++) { if(max < arr[i]){ max = arr[i]; maxp = i; } cur_sum += arr[i]; if(cur_sum < 0) { cur_sum = 0; start = i+1; } else flag = 1; if(maxsum < cur_sum) { maxsum = cur_sum; end = i; } } //This is the case when all elements are negative if(flag == 0) { printf("Max sum subarray = {%d}\n",arr[maxp]); return; } printf("Max sum subarray = {"); for(int i=start;i<=end;i++) printf("%d ",arr[i]); printf("}\n"); } 

Answer 11

Here is a solution in Go using the Kadan algorithm

 func maxSubArr(A []int) (int, int, int) { start, currStart, end, maxSum := 0, 0, 0, A[0] maxAtI := A[0] for i := 1; i < len(A); i++ { if maxAtI > 0 { maxAtI += A[i] } else { maxAtI = A[i] currStart = i } if maxAtI > maxSum { maxSum = maxAtI start = currStart end = i } } return start, end, maxSum }