Teile und Herrsche, längstes absteigendes Teilarray bestimmen

[yeha]

hey 🙂
ich versuch mich grade an Teile und Herrsche und bekomme die Aufgabe ums verrecken nicht hin. Vielleicht kann mir hier ja jemand einen Ansatz geben, wie ich die Aufgabe am besten lösen kann.
Meiner war, zu überprüfen ob das längste Teilarray in der linken bzw. rechten Hälfte oder in der "Mitte" vorkommt. Jedoch funktioniert bisher kein Fall bei mir...
hier mein Code: //ja ich weiß, er ist schlecht 😀

    public static int longestSubArray(int[]array,int left,int right)
    {
        int q=(right+left)/2;
        if(array.length==0)
        {
            return 0;
        }
        if(array.length==1)
        {
            return 1;
        }
        if(left==right)
        {
            return 0;
        }
        if(left==q)
        {
            return 0;
        }
        if(right==q)
        {
            return 0;
        }
        if(array[left]>=longestSubArray(array,left+1,q))
        {
            return longestSubArray(array,left+1,q)+1;
        }
        else
        {
            return longestSubArray(array,q+1,right)+1;
        }
       
}

Ob er in der Mitte vorkommt, habe ich bisher noch gar nicht implementiert, wie man sehen kann.

 

[JStein52]

ob das längste Teilarray in der linken bzw. rechten Hälfte oder in der "Mitte" vorkommt.

Ich verstehe gerade nicht was du da machen willst. Was ist ein "längstes Teilarray" ?

 

[yeha]

ich möchte das längste, absteigende Teilarray bestimmen: in dem Array : -1, 0, 3, 2 , 1 , 5
wäre die Länge 3 wegen 3>2>1

 

[Flown]

das längste absteigende Teilarray, das in einem Stück drinnen liegt oder kann das auch verteilt sein?

 

[yeha]

genau, es soll zusammenhängend sein

 

[JStein52]

und das soll dann ein Sortieralgorithmus werden ?

 

[yeha]

nein, ich soll die Länge der maximalen, absteigenden, zusammenhängenden Folge bestimmen, mittels Teile & Herrsche

 

[JStein52]

können Zahlen auch mehrfach vorkommen ?

 

[yeha]

ja

 

[yeha]

ich hab den Code mal etwas erweitert. Die methode longHelp funktioniert aber anscheinend nicht korrekt.

public static int longestSubArray(int[]array,int left,int right)
    {
        int q=(right+left)/2;
        if(array.length==0)
        {
            return 0;
        }
        if(array.length==1)
        {
            return 1;
        }
        if(left==right)
        {
            return 0;
        }
        if(left==q)
        {
            return 0;
        }
        if(right==q)
        {
            return 0;
        }
        if(longHelp(array,q+1,right)>longHelp(array,left,q))
        {
            return longHelp(array,q+1,right);
        }
        else if(array[q]>array[q+1])
        {
            return longHelp(array,q+1,right)+longHelp(array,left,q);
        }
        else
        {
            return longHelp(array,left,q);
        }
       
       
}
   
    public static int longHelp(int[] array,int left,int right)
    {
        if(array.length==0)
        {
            return 0;
        }
        if(array.length==1)
        {
            return 1;
        }
        if(left==right)
        {
            return 0;
        }
       
        else
        {
            if(array[left]>=longHelp(array,left+1,right))
            {
                return longHelp(array,left+1,right)+1;       
            }
            else
            {
                return 0;
            }
           
            }
       
    }

 

[yeha]

Niemand der mir dabei helfen kann? :/

 

[Flown]

Ich weiß nicht wieso das ein Divide&Conquer Algorithmus ist, wenn man was sequentiell verarbeiten muss. Wie sieht denn dein Plan dazu aus? In PseudoCode oder auch als Skizze?

 

[yeha]

Tja das war eben die Aufgabe. Ich habe meinen Code ja bereits gepostet.
In Pseudocode müsste der so ähnlich aussehen.