trouver le début et la fin de l'index pour un max de sous tableau

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



    }

}

ce programme génère le max de la somme de sous-tableau ..dans ce cas, les 19,à l'aide de {5,9,-5,10}..
maintenant, je dois trouver le début et la fin de l'index de ce tableau ..comment dois-je faire ??

Whats est votre sortie attendue pour cet? La Question n'est pas claire
Aller pour le kadane algorithme.. maximale de la sous-matrice linéaire de la complexité...

OriginalL'auteur user1896796 | 2013-01-06

java

Comme Ce

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, donc, il y a un problème dans la solution ci-dessus comme l'a souligné Steve P. C'est une autre solution qui devrait fonctionner pour tous les

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

Ce n'est pas correct, pensez list = [631, -583, -975]
Hey. Juste assez. J'ai ajouté une autre solution qui fonctionne pour tous les
N'est pas votre deuxième solution est l'heure de la complexité est O(n2) ?
Yep. Probablement à réviser que pour faire mieux ...

OriginalL'auteur cjds

C'est un programme en C pour résoudre ce problème. Je pense que la logique est la même pour toutes les langues, donc je l'ai posté cette réponse.

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

C'est un programme en C pour résoudre ce problème. Je pense que la logique est la même pour toutes les langues donc je l'ai posté cette réponse. Je pense que cela peut être utile pour vous.
très belle solution

OriginalL'auteur Kishore Kumar

Fixation Carl Saldanha solution:

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

OriginalL'auteur Lem0n

1

La question est un peu floue mais je devine un "sous-ensemble" est la moitié de l'arr objet.

Une lame de façon à le faire comme ceci
```
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);
}
```
J'ai cette image peut ne pas fonctionner si l'arr contient un nombre impair d'éléments.

Si vous souhaitez accéder à un niveau plus élevé de soutien convertir le primvate tableaux à un objet de la Liste d'
```
List<Integer> list = Arrays.asList(arr);
```
Cette façon, vous avez accès à un ensemble des fonctionnalités de l'objet.

Aussi, si vous avez le temps, jetez un oeil à l'ordre supérieur fonctionnel appelé réduire. Vous aurez besoin d'une bibliothèque qui prend en charge la programmation fonctionnelle. La goyave ou lambdaJ pourrait avoir une réduction de la méthode. Je sais que apache commons manque un, sauf si vous voulez pirater ensemble.

OriginalL'auteur Dan

Voici algorithme pour 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);
}

}

OriginalL'auteur Saurabh Jain

Voici une solution en python - Kadane de l'algorithme de étendu pour imprimer le début/la fin de l'index

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)

OriginalL'auteur sysuser

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

OriginalL'auteur Nitin Jha

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

il ne parvient pas pour les nombres négatifs { -631, -583, -9000,-975, -7100}

OriginalL'auteur Kartik

0

La seule chose que j'ai à ajouter (à plusieurs solutions posté ici) est de couvrir les cas que tous les entiers sont négatifs, auquel cas le max de sous tableau sera juste le max élément. Assez facile à faire.. suffit de suivre max élément et l'indice de l'indice de la puissance maximum de l'élément que vous itérer dessus. Si le max élément est négatif, il retourne l'indice de la place.

Il y a aussi le cas de débordement pour éventuellement gérer. J'ai vu algorithme de tests qui prennent de compte.. c'est à dire, supposons exemple maxint a été l'un des éléments et vous avez tenté d'ajouter. Je crois que certains de la Codility (codage interview concasseur) tests d'en tenir compte.

OriginalL'auteur crig

Un O(n) en solution dans C serait :-

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

OriginalL'auteur Dipayan

Voici une solution en utilisant Kadane l'Algorithme de

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
}

OriginalL'auteur K. Ali

Vous devez vous connecter pour publier un commentaire.