finden Sie die start-und end-index für eine max sub-array

Wie Diese

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, es gab ein problem bei der obigen Lösung als wies auf Steve P. Dies ist eine weitere Lösung, die funktionieren sollte für alle

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

Hier ist der Algorithmus für maxsubarray:

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

}

Die Frage ist etwas unklar, aber ich vermute, eine "sub-array" ist die Hälfte der arr-Objekt.

Einen Lahmen Weg, dies zu tun, wie dies

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

Ich dieses Bild könnte nicht funktionieren, wenn die arr enthält eine ungerade Anzahl von Elementen.

Wenn Sie möchten, den Zugang zu einem höheren level-support, konvertieren Sie die primvate arrays, um eine Liste Objekt

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

Diese Weise haben Sie Zugriff auf ein collection-Objekt-Funktionalität.

Auch, wenn Sie Zeit haben, werfen Sie einen Blick auf die höhere Ordnung, die funktionale genannt reduzieren. Sie müssen eine Bibliothek, unterstützt die funktionale Programmierung. Guave oder lambdaJ vielleicht eine Methode reduzieren. Ich weiß, dass der apache-commons-fehlt einer, es sei denn, Sie wollen zu hacken, um es zusammen.

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

Das einzige, was ich noch hinzufügen (mehrere Lösungen hier gepostet) ist, um den Fall abzudecken, dass die zahlen negativ sind, in welchem Fall die max sub-array wird nur die max-element. Ziemlich einfach zu machen.. nur zu verfolgen max-element und index der index des max-element, wie Sie Durchlaufen wird. Wenn die max-element negativ ist, wieder in den index statt.

Es ist auch der Fall von overflow eventuell zu behandeln. Ich habe gesehen, Algorithmus-tests als in Konto.. D.H., angenommen, MAXINT war eines der Elemente, und Sie versucht, um es hinzuzufügen. Ich glaube, dass einige der Codility (coding interview Screener) tests, die Rechnung zu tragen.

Hier ist eine Lösung, bei Gehen mit Kadane-Algorithmus

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
}