Wyobraźmy sobie, że otrzymujemy kawałek jakiegoś górzystego regionu, co dałoby kształt podobny do tego:

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

Jak widzimy, możemy to przedstawić (do pewnego stopnia) za pomocą sekwencji liczb całkowitych.

Na potrzeby tego wyzwania definiujemy dolinę jako ciągłą podsekwencję, w której wartości początkowo maleją, a od pewnego momentu rosną. Bardziej formalnie dla sekwencji doliną będą indeksy dla których:$(a_i)_{i=1}^n$$1 \leq s < r < t \leq n$

• punkt początkowy i końcowy doliny są takie same:$a_s = a_t$
• dolina zaczyna się i kończy, gdy region obniży się:$a_s > a_{s+1} \land a_{t-1} < a_t$
• dolina nie jest płaska:$a_s \neq a_r \land a_r \neq a_t$
• dolina początkowo zmniejsza się:$\forall i \in [s,r): a_i \geq a_{i+1}$
• dolina w pewnym momencie wzrośnie:$\forall j \in [r,t): a_j \leq a_{j+1}$

Teraz definiujemy szerokość takiej doliny jako wielkość wskaźników , tj. .$[s,t]$$t-s+1$

Wyzwanie

Biorąc pod uwagę profil wysokości (sekwencja liczb całkowitych nieujemnych), Twoim zadaniem jest określenie szerokości najszerszej doliny.

Przykład

Biorąc pod uwagę profil wysokości [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], możemy go wizualizować jak poprzednio:

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

Zwróć uwagę, że druga dolina [3,2,1,0,0,1,2,2,3]nie rozciąga się bardziej na prawo, ponieważ skrajnie lewy punkt to a nie . Ponadto nie dodajemy pozostałych dwóch s, ponieważ wymagamy, aby punkt końcowy był wyżej niż punkt przedostatni.$3$$4$$3$

Dlatego szerokość najszerszej doliny wynosi .$9$

Zasady

• Dane wejściowe będą ciągiem liczb całkowitych nieujemnych (przepraszam Holendrów)
  • możesz założyć, że zawsze jest co najmniej jedna dolina
• Wyjściowy będzie rozmiar najszerszej doliny, jak zdefiniowano powyżej

Przypadki testowe

[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

Galaretka , 15 bajtów

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

Wypróbuj online!

Lub zobacz pakiet testowy (dodano dwa kolejne przypadki testowe, których wcześniej nie wypełniałem).

W jaki sposób?

Ẇµ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 bajtów

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

Wypróbuj online!

Skomentował

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 bajtów

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

Wypróbuj online!

Retina 0.8.2 , 77 bajtów

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

O^`
\G,|$

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

M&!`

Wymień, a nie licząc, nakładające się mecze.

\b(1+),

Początek doliny jest uchwycony \1. To nie może się powtórzyć do końca. Ponieważ nie przechwytujemy przecinka, zapobiega to również dopasowaniu wyższych wartości.

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

Dopasuj malejące wartości. (?!1+\2)Zapobiega żadnego przejścia przez pętlę z jest większe niż poprzednie. (Pierwszy raz \2nie jest ustawiony, więc nie pasuje trywialnie.) Przechwytywanie obejmuje przecinek końcowy, ponieważ jest to golfier.

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

Dopasuj rosnące wartości. Ten czas ((?3)\3|\2)oznacza, że ​​każde dopasowanie musi być co najmniej tak długie, jak poprzednia wartość lub ostatnie malejące przechwytywanie za pierwszym razem przez pętlę.

\1\b

Wreszcie koniec doliny musi być tej samej wysokości co początek.

1

Usuń wysokości, pozostawiając przecinki. (Jest to nieco łatwiejsze niż liczenie wysokości, ponieważ niektóre z nich mogą wynosić zero).

O^`

Sortuj w odwrotnej kolejności, tzn. Najpierw większość przecinków.

\G,|$

Policz liczbę przecinków w pierwszym wierszu plus jeden.

Łuska , 13 bajtów

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

Wypróbuj online!

Wyjaśnienie

Używam podobnego algorytmu jak 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 bajtów

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

Wypróbuj online!

Oszczędź 10 bajtów, czerpiąc inspirację z odpowiedzi Łuski Zgarba. Nadal uważam, że można to poprawić, ale jeszcze go nie znalazłem.

Wyjaśnienie:

¡ã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