Bayangkan kita mendapatkan sepotong daerah pegunungan, ini akan menghasilkan bentuk yang mirip dengan ini:

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

Seperti yang dapat kita lihat, kita dapat mewakili ini (sampai tingkat tertentu) dengan urutan bilangan bulat.

Untuk tujuan tantangan ini kami mendefinisikan lembah sebagai urutan yang berdekatan di mana nilai awalnya menurun dan dari beberapa titik mereka meningkat. Lebih formal untuk urutan lembah akan menjadi indeks yang dipegang oleh yang berikut:$(a_i)_{i=1}^n$$1 \leq s < r < t \leq n$

• awal dan titik akhir lembah sama:$a_s = a_t$
• lembah dimulai dan berakhir begitu wilayah menjadi lebih rendah:$a_s > a_{s+1} \land a_{t-1} < a_t$
• lembah tidak datar:$a_s \neq a_r \land a_r \neq a_t$
• lembah awalnya berkurang:$\forall i \in [s,r): a_i \geq a_{i+1}$
• lembah pada suatu titik akan meningkat:$\forall j \in [r,t): a_j \leq a_{j+1}$

Sekarang kita mendefinisikan lebar lembah seperti ukuran indeks , yaitu. .$[s,t]$$t-s+1$

Tantangan

Diberikan profil tinggi (urutan bilangan bulat non-negatif), tugas Anda adalah menentukan lebar lembah terluas.

Contoh

Mengingat profil tinggi [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], kami dapat memvisualisasikannya seperti sebelumnya:

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

Perhatikan bagaimana lembah kedua [3,2,1,0,0,1,2,2,3]tidak meluas lebih jauh ke kanan karena titik paling kiri adalah dan bukan . Selain itu kami tidak menambahkan dua tersisa karena kami mengharuskan titik akhir lebih tinggi dari titik kedua-terakhir.$3$$4$$3$

Karena itu, lebar lembah terluas adalah .$9$

Aturan

• Input akan menjadi urutan bilangan bulat non-negatif (maaf orang Belanda)
  • Anda dapat mengasumsikan bahwa selalu ada setidaknya satu lembah
• Output akan menjadi ukuran lembah terluas seperti yang didefinisikan di atas

Testcases

[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

Jelly , 15 byte

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

Cobalah online!

Atau lihat test-suite (menambahkan dua lagi test case yang sebelumnya gagal saya penuhi).

Bagaimana?

Ẇµ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

Cobalah online!

Berkomentar

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 byte

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

Cobalah online!

Retina 0.8.2 , 77 byte

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

O^`
\G,|$

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

\d+
$*

Konversikan ke unary.

M&!`

Daftar, daripada menghitung, pertandingan yang tumpang tindih.

\b(1+),

Mulai lembah ditangkap \1. Maka ini harus tidak cocok lagi sampai akhir. Karena kami tidak menangkap koma, ini juga mencegah pencocokan nilai yang lebih tinggi.

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

Cocokkan dengan nilai yang menurun. The (?!1+\2)mencegah lulus apapun melalui loop dari menjadi lebih besar dari sebelumnya. (Pertama kali melalui \2tidak diatur sehingga gagal untuk mencocokkan sepele.) Tangkapan termasuk koma tertinggal karena itu golfier.

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

Cocokkan dengan nilai yang meningkat. Waktu ini ((?3)\3|\2)berarti bahwa setiap pertandingan harus setidaknya selama nilai sebelumnya, atau tangkapan menurun terakhir kali pertama melalui loop.

\1\b

Akhirnya ujung lembah harus sama tingginya dengan awal.

1

Hapus ketinggian, tinggalkan koma. (Ini sedikit lebih mudah daripada menghitung ketinggian karena beberapa dari mereka mungkin nol.)

O^`

Sortir dalam urutan terbalik yaitu sebagian besar koma terlebih dahulu.

\G,|$

Hitung jumlah koma pada baris pertama, ditambah satu.

Sekam , 13 byte

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

Cobalah online!

Penjelasan

Saya menggunakan algoritma yang mirip dengan 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 byte

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

Cobalah online!

Menyimpan 10 byte dengan mengambil inspirasi dari jawaban Husk Zgarb. Saya masih berpikir ini bisa diperbaiki, tetapi saya belum menemukannya.

Penjelasan:

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