user1896796 user1896796 - 5 months ago 11
Java Question

finding the start and end index for a max sub array

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 max sum of sub array ..in this case its 19,using {5,9,-5,10}..
now i have to find the start and end index of this sub array ..how do i do that ??

Answer

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

Okay so there was a problem in the above solution as pointed to Steve P. This is another solution which should work for all

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