# Lokale Maxima und Minima in Wertereihe



## marub (21. Jan 2010)

Hallo zusammen!

folgendes Problem: ich habe eine Reihe von Werten (knapp 10.000 Stück) in einer Arraylist und brauche jetzt die lokalen Maxima und die darauf folgenden Minima. Das Problem bei der Sache ist, dass manchmal auch mehrmals der gleiche Wert nacheinander folgt. Mein erster Ansatz (siehe unten) schlägt damit in diesen Spezialfällen fehl und schreibt auch Max/Min raus die eigentlich auf einer Art Plateau liegen

```
ArrayList<Double> max = new ArrayList<Double>();
ArrayList<Double> min = new ArrayList<Double>();
    	int i=1;
    	do
    	{
    		if (werte.get(i-1)<=werte.get(i)) 
        	{
    			if (werte.get(i+1)<werte.get(i))
    			{
    				max.add(werte.get(i));
    			}
    		}
        	if (werte.get(i-1)>=werte.get(i))
        	{
        		if (werte.get(i+1)>werte.get(i))
        		{
        			min.add(werte.get(i));
        		}
        	}
    		i++;
    	}
    	while(i<werte.size()-2);
```

Weiß jemand Rat? Danke im Vorraus!


----------



## Tomate_Salat (21. Jan 2010)

ich könnte mich durchaus irren, aber für mich sieht das aus als ob du die werte kopierst und ca. 2x in jedes der beiden ArrayLists packst. Auch ist mir deine Frage niciht ganz klar. Willst du die höchste und die niedrigste zahl in dem ganzen? Willlst du das jede Zahl nur einmal vorkommen kann?!

Wenn du die größte/kleinste Zahl ausgeben willst, dann würde ich mir eine eigene Klasse schreiben die von ArrayList erbt mit 2 zusätzlichen Objektvariablen: [c]int max,min;[/c]. Wenn du werte zuweiste, dürfte es kein Problem sein, zu Prüfen, ob du hier eine kleinste/größte Zahl vor dir liegen hast.

Willst auch dass jede Zahl nur einmal vorkommt und nicht öfters gespeichert wird, so kann man das meines wissens nach, glaub ich mit [c]TreeSet[/c] lösen. In dem Falle würde ich also [c]ArrayList[/c] durch ein [c]TreeSet[/c] ersetzen (auch in dem Klassenbeispiel oben)

MFG

Tomate_Salat


----------



## marub (21. Jan 2010)

wie schon gesagt ich suche die lokalen maxima und minima. ein beispiel zeigt, was ich will:

eine wertereihe: 2 4 5 6 8 6 5 7 9 10 12 13 10 10 9 8 6 7 9 13 15 17 17 15 14 14 13 15 16 ...

jetzt möchte ich in der einen arraylist die lokalen max haben, also: 8, 13, 17
und in der anderen die lokalen min (die 2 als startwert mal außenvorgelassen): 5, 6, 13

hoffe jetzt ist das problem ein wenig klarer! wenn aufeinander folgende zahlen nicht gleich wären, würde der code laufen (tut er so auch aber er schreibt halt zuviele zahlen raus)


----------



## Tomate_Salat (21. Jan 2010)

nun ja ich klink mich aus, ich denke dein Problem ist klar, nur habe ich trotzdem keine Ahnung was da rauskommen soll.


----------



## marub (21. Jan 2010)

also die ermittelten zahlen können natürlich doppelt vorkommen, wenn es also mehrer lokale minima mit dem wert 5 geben sollte, dann sollen die auch in der auflistung der minima an der richtigen stelle stehen.


----------



## Marco13 (21. Jan 2010)

Ich glaube es geht nur um ein paar Definitionen. 

Bei einer Liste mit Werten x0,x1...xn sollen in der Liste der Maxima am Ende genau die Werte stehen, für die gilt: [...hier die Bedingung einsetzen...]


----------



## marub (21. Jan 2010)

..., für die gilt, dass diese Werte die Gipfel / Peaks / lokalen Maxima der Wertereihe darstellen und zwar in der Reihenfolge in der sie auch in der Wertereihe auftreten.´

wenn ich ein glas habe, das mal gefüllt wird ,aus dem mal getrunken wird oder auch mal ne zeit lang nur rumsteht, sind die lokalen maxima der glasinhalt, kurz bevor (nach einer füllung bzw. nach einer füllung + verharrzeit) mal wieder getrunken wird. find ich jetzt ehrlich gesagt nicht allzu schwer zu verstehn, was ich mit lokalen maxima meine und das bsp oben machts ja auch klar.


----------



## SlaterB (21. Jan 2010)

du musst zu jedem Zeitpunkt 2 Indexe merken, und zwar die der beiden letzten unterschiedlichen Werte

bei einer Reihe 10, 10, 11, 11, 10
fängst du mit der 10 an, erster Wert, Index 0 merken, nix weiter tun,
als nächstes noch ne 10, ignorieren da sie dem letzten Index entspricht (Achtung: nicht dem zweiten, sondern den ersten),
als nächstes die 11, endlich eine zweite Zahl vorhanden, als zweiten Index die 2 merken,
sonst nix weiter machen

nächste Zahl wieder 11, entspricht der am letzten Index (ab jetzt immer der zweite), nix machen

als nächstes die 10, diese entspricht nicht der letzten, es liegen nun also drei verschiedene Werte vor,
gegebenenfalls Min/ Max merken,
dann die beiden Indexe weiterrücken

fertig, so gehts weiter bis zum Ende


----------



## Marco13 (21. Jan 2010)

Vielleicht hätte ich expliziter sein sollen. In der Bedingung sollten keine Worte vorkommen. Das, was du bisher hast, wäre [c]{ x(n) | x(n-1) <= x(n) & x(n+1) > x(n) }[/c]. Bei einer Folge wie [c]1 2 2 2 1[/c] steht da dann halt [c]2[/c] drin. Damit dort in diesem Fall nichts drinsteht, müßte die Bedingung [c]{ x(n) | x(n-1) < x(n) & x(n+1) > x(n) }[/c] sein.


----------



## Tomate_Salat (21. Jan 2010)

achso, ja ich glaub ich habs kapiert:

n steigt. Iwann ist n+1 < n, dort ist ein lokales maxima. Danach sinkt der wert und iwann ist n < n+1, indem fall haben wir ein lokales minima. 

ungetestet:


```
boolean steigt = ( werte.get(0) < werte.get(1) );

for(int i=1; i < werte.size()-1; i++)
{
     if(steigt)
    {
          if(werte.get(i+1) < werte.get(i)) 
         {
              max.add(werte.get(i));
              steigt = false;
         }
    }
    else
    {
         if(werte.get(i+1) > werte.get(i)) 
         {
              min.add(werte.get(i));
              steigt = true;
         } 
    }
}
```

ka ob das obenstehende funktioniert


----------



## SlaterB (21. Jan 2010)

hmm, abgesehen vom noch zu behebenen Problem bei zwei gleichen Zahlen zu Beginn klingt das einfacher als meine Idee


----------



## Tomate_Salat (21. Jan 2010)

```
int start = 0;
while(werte.get(start) == werte.get(start+1)) start++;

for(int i = start...
```


----------



## Marco13 (21. Jan 2010)

Ist bei einer Folge wie [c]1 2 3 4[/c] die 1 ein lokales Minimum und die 4 ein lokales Maximum?


----------



## marub (21. Jan 2010)

habs glaub ich schon gelöst, eben noch testen bevor ich hier mist reinstelle...


----------



## SlaterB (21. Jan 2010)

@Marco13
macht das Sinn, die ganze Zeit nach unverständlichen Definitionen zu fragen?
der Code aus dem ersten Posting ist da doch recht deutlich,
bei Details kann marub das auch immer noch anpassen noch nachfragen


----------



## marub (21. Jan 2010)

Läuft, trotzdem danke an alle für die Beiträge!

```
int i=0;
    	double maxi=0;
    	double mini=0;
    	ArrayList<Double> max = new ArrayList<Double>();
    	ArrayList<Double> min = new ArrayList<Double>();
    	do
    	{
    		if (werte.get(i)<=werte.get(i+1))
    		{
    			maxi=werte.get(i+1);
    			i++;
    		}
    		else
    		{
    			max.add(maxi);
    			System.out.println("maxi = "+maxi);
    			while(werte.get(i)>=werte.get(i+1) && i<werte.size()-2)
    			{
    				mini=werte.get(i+1);
    				i++;
    			}
    			min.add(mini);
    			System.out.println("mini = "+mini);
    		}
    	}
    	while(i<werte.size()-2);
```


----------

