Stellen Sie sich vor, wir erhalten einen Ausschnitt aus einer Bergregion. Dies würde eine ähnliche Form ergeben:

4                   _
3   _    _       __/ \
2  / \__/ \    _/     \_   /
1 /        \  /         \_/
0           \/
  12322223210012233343221112

Wie wir sehen können, können wir dies (bis zu einem gewissen Grad) mit einer Folge von ganzen Zahlen darstellen.

Für diese Herausforderung definieren wir ein Tal als eine zusammenhängende Folge, in der die Werte anfänglich abnehmen und ab einem bestimmten Punkt zunehmen. Formal für eine Folge $(a_i)_{i=1}^n$ ein Tal Indizes für die gilt:$1 \leq s < r < t \leq n$

• Start- und Endpunkt des Tals sind gleich:$a_s = a_t$
• Das Tal beginnt und endet, sobald die Region niedriger wird:$a_s > a_{s+1} \land a_{t-1} < a_t$
• das tal ist nicht flach:$a_s \neq a_r \land a_r \neq a_t$
• das Tal nimmt anfangs ab:$\forall i \in [s,r): a_i \geq a_{i+1}$
• das Tal wird sich irgendwann erhöhen:$\forall j \in [r,t): a_j \leq a_{j+1}$

Nun definieren wir die Breite eines solchen Tals als die Größe der Indizes , dh. t-s + 1 .$[s,t]$$t-s+1$

Herausforderung

Bei einem vorgegebenen Höhenprofil (Folge nicht negativer Ganzzahlen) besteht Ihre Aufgabe darin, die Breite des breitesten Tals zu bestimmen.

Beispiel

Aufgrund des Höhenprofils [1,2,3,2,2,2,2,3,2,1,0,0,1,2,2,3,3,3,4,3,2,2,1,1,1,2]können wir es wie bisher visualisieren:

4                   _
3   _    _       __/ \
2  / \__/ \    _/     \_   /
1 /        \  /         \_/
0           \/
  12322223210012233343221112
    aaaaaa             ccccc
         bbbbbbbbb

Beachten Sie, dass sich das zweite Tal [3,2,1,0,0,1,2,2,3]nicht weiter nach rechts erstreckt, da der am weitesten links liegende Punkt und nicht . Außerdem addieren wir die verbleibenden zwei s nicht, da der Endpunkt höher als der vorletzte Punkt sein muss.$3$$4$$3$

Daher beträgt die Breite des breitesten Tals .$9$

Regeln

• Die Eingabe besteht aus einer Folge nicht negativer Ganzzahlen (entschuldige Holländer)
  • man kann davon ausgehen, dass es immer mindestens ein tal gibt
• Die Ausgabe hat die oben definierte Größe des breitesten Tals

Testfälle

[4,0,4] -> 3
[1,0,1,0,1] -> 3
[1,0,2,0,1,2] -> 4
[13,13,13,2,2,1,0,1,14,2,13,14] -> 4
[1,2,3,2,2,2,2,3,2,1,0,0,1,2,2,3,3,3,4,3,2,2,1,1,1,2] -> 9
[3,2,0,1,0,0,1,3] -> 4

Gelee , 15 Bytes

ẆµIṠḟ0ṢƑaMIḢ)Ṁ‘

Probieren Sie es online!

Oder sehen Sie sich eine Testsuite an (fügen Sie zwei weitere Testfälle hinzu, die ich zuvor nicht erfüllt habe).

Wie?

ẆµIṠḟ0ṢƑaMIḢ)Ṁ‘ - Link: list of integers
Ẇ               - all contiguous substrings
 µ          )   - for each substring, X:
  I             -   deltas
   Ṡ            -   sign (-ve:-1, 0:0, +ve:1)
    ḟ0          -   filter out zeros
       Ƒ        -   is invariant under:
      Ṣ         -     sort
         M      -   get maximal indices of X
        a       -   (vectorising) logical AND
          I     -   deltas
           Ḣ    -   head
             Ṁ  - maximum
              ‘ - increment

JavaScript (ES6), 111 108 99 97 Byte

a=>a.map(o=(p,x)=>a.some(P=q=>(~x?x<0?i?q<P:q>P&&i++:i=0:q>=p)||(o=o<--x|q==P|q-p?o:x,P=q,0)))|-o

Probieren Sie es online!

Kommentiert

a =>                        // a[] = input array
  a.map(o =                 // initialize the output o to a non-numeric value
    (p, x) =>               // for each value p at position x in a[]:
    a.some(P =              //   initialize P to a non-numeric value
      q =>                  //   for each value q in a[]:
      (                     //     exit if something goes wrong:
        ~x ?                //       if x is not equal to -1:
          x < 0 ?           //         if x is negative:
            i ?             //           if we're in the increasing part:
              q < P         //             exit if q is less than P
            :               //           else:
              q > P && i++  //             increment i if q is greater than P
          :                 //         else:
            i = 0           //           initialize i to 0 (decreasing part)
        :                   //       else:
          q >= p            //         exit if q is greater than or equal to p
      ) || (                //     if we didn't exit:
        o =                 //       update the output o:
          o < --x |         //         decrement x; if o is less than x
          q == P |          //         or the last value is equal to the previous one
          q - p ?           //         or the last value is not equal to the first one
            o               //           leave o unchanged
          :                 //         else:
            x,              //           update o to x
        P = q,              //       update the previous value P to q
        0                   //       force this iteration to succeed
      )                     //
    )                       //   end of some()
  ) | -o                    // end of map(); return -o

Python 2 , 120 115 89 87 86 152 149 Bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if max(a[l+1:r]+[0])<v==w*any(s(a[l:i])[::-1]+s(a[i:r])==a[l:r]for i,_ in e(a)));e=enumerate;s=sorted

Probieren Sie es online!

Retina 0.8.2 , 77 Bytes

\d+
$*
M&!`\b(1+),((?!\1)(?!1+\2)1*,)+((?!\1)1*(?(3)\3|\2))*\1\b
1

O^`
\G,|$

Probieren Sie es online! Link enthält Testfälle. Erläuterung:

\d+
$*

In Unary konvertieren.

M&!`

Listen Sie Übereinstimmungen auf, anstatt sie zu zählen.

\b(1+),

Der Talanfang wird erfasst \1. Dies muss dann erst zum Schluss wieder passen. Da wir das Komma nicht erfassen, wird auch verhindert, dass höhere Werte übereinstimmen.

((?!\1)(?!1+\2)1*,)+

Passen Sie die abnehmenden Werte an. Das (?!1+\2)verhindert , dass die jeden Durchlauf durch die Schleife aus größer ist als die vorherige. (Der erste Durchgang \2ist nicht festgelegt, sodass er nicht trivial übereinstimmt.) Die Erfassung enthält das nachgestellte Komma, da dies Golfspieler sind.

((?!\1)1*(?(3)\3|\2))*

Passen Sie die ansteigenden Werte an. Diese Zeit ((?3)\3|\2)bedeutet, dass jede Übereinstimmung mindestens so lang sein muss wie der vorherige Wert oder die letzte abnehmende Erfassung beim ersten Durchlauf der Schleife.

\1\b

Schließlich muss das Talende die gleiche Höhe wie der Start haben.

1

Löschen Sie die Höhen und lassen Sie die Kommas. (Dies ist etwas einfacher als das Zählen der Höhen, da einige von ihnen Null sein könnten.)

O^`

In umgekehrter Reihenfolge sortieren, dh die meisten Kommas zuerst.

\G,|$

Zählen Sie die Anzahl der Kommas in der ersten Zeile plus eins.

Schale , 13 Bytes

→▲mΓ€fȯΛEtġ≤Q

Probieren Sie es online!

Erläuterung

Ich benutze einen ähnlichen Algorithmus wie Jonathan Allan .

→▲mΓ€fȯΛEtġ≤Q  Input is a list, say [3,1,0,1,1,0,2,3]
            Q  Nonempty slices: [[3],[1],[3,1],[0],...,[3,1,0,1,1,0,2,3]]
     f         Keep those that satisfy this:
                Argument is a slice, say [3,1,0,1,1,0,2]
          ġ≤    Cut into non-increasing pieces: [[3,1,0],[1,1,0],[2]]
         t      Drop first piece: [[1,1,0],[2]]
      ȯΛ        Each remaining piece
        E       has all elements equal: false, [1,1,0] has different elements
  m            Map over remaining slices:
                Argument is a slice, say [1,0,1,1]
   Γ            Break into head 1 and tail [0,1,1]
    €           Index of first occurrence of head in tail: 2
 ▲             Maximum: 2
→              Increment: 3

Japt , 31 Bytes

¡ãYÄÃrc k_ò< Åd_äa x}îbZvÃrÔ+2

Probieren Sie es online!

Sparte 10 Bytes, indem du dich von Zgarbs Antwort auf "Husk" inspirieren ließest. Ich denke immer noch, dass dies verbessert werden kann, aber ich habe es noch nicht gefunden.

Erläuterung:

¡ãYÄÃrc                            Get all segments
        k_           Ã             Remove ones where:
          ò<                        A non-increasing sub-segment
             Å                      Other than the first one
              d_äa x}               Has different heights
                      ®   Ã        For each remaining segment:
                       bZv          Get the second index of the first character
                           rÔ      Maximum
                             +2    Increase by 2