tło

Chcę kupić działkę i zbudować na niej mój dom. Mój dom powinien być prostokątny i tak duży, jak to możliwe; jednak dostępne działki mają wiele skalistych obszarów, na których nie mogę zbudować, i mam problem z dopasowaniem potencjalnego domu na działkach. Chcę, żebyś napisał program, który analizuje dla mnie wykresy.

Wejście i wyjście

Twoje dane wejściowe to prostokątna tablica 2D bitów o wielkości co najmniej 1 × 1, w dowolnym rozsądnym formacie. Tablica przedstawia działkę; 1s są „dobrymi” obszarami, w których mógłbym zbudować mój dom, i 0s są „kamienistymi” obszarami, w których domu nie można zbudować.

Twój wynik powinien być maksymalnym obszarem pełnego prostokąta 1sw tablicy wejściowej. Reprezentuje powierzchnię największego domu, jaki mogłem zbudować na działce. Zauważ, że jeśli 1na wejściu nie ma żadnych znaków, to wynikiem jest 0.

Przykład

Rozważ dane wejściowe

101
011
111

Największy prostokąt 1s to prostokąt 2 × 2 w prawym dolnym rogu. Oznacza to, że poprawne wyjście to 4.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12

Galaretka , 21 20 18 17 bajtów

ṡṂ€€×"
‘×¥\ç"Ụ€FṀ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Niech M będzie macierzą bitów takich jak

0 0 0 1 1 0 0 0 0
1 1 0 1 1 0 0 1 0
1 1 0 1 1 1 1 1 0
1 1 0 0 1 1 1 0 0
0 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0

Zaczynamy od zliczenia liczby 1 bitów w każdej kolumnie M , resetując liczbę za każdym razem, gdy napotkamy 0 bit.

Dla naszej przykładowej macierzy daje to

0 0 0 1 1 0 0 0 0
1 1 0 2 2 0 0 1 0
2 2 0 3 3 1 1 2 0
3 3 0 0 4 2 2 0 0
0 4 0 0 5 3 3 1 1
1 5 1 1 6 4 4 2 2
2 6 2 2 0 5 5 3 0

Następnie obliczamy wszystkie sąsiadujące podlisty każdego wiersza. Osiągamy to, generując wszystkie wycinki długości k , gdzie k zmienia się między 1 a liczbą wpisów w każdym rzędzie.

W przypadku przedostatniego rzędu daje to

[1], [5], [1], [1], [6], [4], [4], [2], [2]
[1, 5], [5, 1], [1, 1], [1, 6], [6, 4], [4, 4], [4, 2], [2, 2]
[1, 5, 1], [5, 1, 1], [1, 1, 6], [1, 6, 4], [6, 4, 4], [4, 4, 2], [4, 2, 2]
[1, 5, 1, 1], [5, 1, 1, 6], [1, 1, 6, 4], [1, 6, 4, 4], [6, 4, 4, 2], [4, 4, 2, 2]
[1, 5, 1, 1, 6], [5, 1, 1, 6, 4], [1, 1, 6, 4, 4], [1, 6, 4, 4, 2], [6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4], [5, 1, 1, 6, 4, 4], [1, 1, 6, 4, 4, 2], [1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4], [5, 1, 1, 6, 4, 4, 2], [1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2], [5, 1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2, 2]

Następnie mapujemy każdy plasterek do iloczynu jego minimum i długości. Dla każdego wycinka oblicza to obszar prostokąta 1 bity o maksymalnej wysokości, który ma dany wycinek jako dolny rząd.

Dla wycinków o długości 3 przedostatniego rzędu naszej przykładowej macierzy daje to

3 3 3 3 12 6 6

Pozostaje tylko wziąć maksimum we wszystkich warstwach wszystkich wierszy.

Dla naszej przykładowej macierzy daje to 12 .

Jak to działa

‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.


ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.

MATL, 32 31 27 bajtów

n:"@:"@1M2$ltntG4$bZ+=a*vX>

Wykorzystuje to podejście oparte na splotach 2D z użyciem siły brutalnej. Wszystkie możliwe rozmiary prostokątów są tworzone i splecione z ukształtowaniem terenu. Maksymalnym wynikiem wszystkich zwojów jest maksymalny obszar prostokąta.

Jest to bardzo nieefektywne rozwiązanie, ponieważ w celu zaoszczędzenia bajtów tworzę jądra dla wszystkich prostokątów pomiędzy, [1, 1]a [numel(input) numel(input)]zamiast faktycznie określając liczbę wierszy / kolumn na wejściu, aby określić właściwe zakresy wymiarów prostokąta.

Dzięki @Luis za sugerowanie użycia Mi pominięcie ]].

Wypróbuj online!

Wyjaśnienie

        % Implicitly grab input as a 2D numeric array
n       % Compute the number of elements in the input (over estimation of max kernel size)
:       % Create array 1:n
"       % For each value
  @     % Current loop index
  :     % Create an array from 1:(current_index)
  "     % For each of these values   
    @   % Push the current index onto the stack
    1M  % Grab the input to the previous function call (the outer index)
    2$l % Create an array of 1's whose dimensions are specified by top two stack elements
    tn  % Duplicate this array and compute number of elements
    t   % Duplicate this number
    G   % Explicitly grab input
    4$b % Bubble up the 4th element from the stack (the kernel)
    Z+  % Perform 2D convolution of this kernel and the input
    =a  % Determine if any convolution result (in each column) is equal to the area of the kernel.
        % This yields a row vector
    *   % Multiply the logical result by the area
    v   % Vertically concatenate all results (forces the row vectors above to be column vectors)
    X>  % Compute the maximum yielding the largest area
        % Implicitly display the result.

Julia, 83 60 57 53 bajtów

!M=M⊆1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

Wypróbuj online! Ostatni przypadek testowy przekracza limit czasu TIO, ale zweryfikowałem go lokalnie.

Jak to działa

Po pierwsze ! sprawdza, czy jej argument macierzy M składa się wyłącznie z 1 .

• Jeśli tak, to ! zwraca sumę wpisów M , która jest równa jego powierzchni.

• Jeśli nie ,! wykonuje następujące czynności:

  1. Obracaj M o 0 ° , 90 ° , 180 ° i 270 ° zgodnie z ruchem wskazówek zegara.

  2. Usunięcia pierwszego rzędu dla każdego z czterech obrotów, skutecznie usuwając jeden z górnym rzędzie dolnym rzędzie, skrajnej lewej kolumnie, z prawej strony kolumnie M .

  3. Nazywaj się rekurencyjnie na każdym z podmacierzy.

  4. Zwraca maksymalną wartość zwracaną z wywołań rekurencyjnych.

JavaScript (ES6), 97 bajtów

a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

Okazuje się, że trochę kręci wciąż wygrywa. Akceptuje tablicę liczb całkowitych. Nie golfowany:

function rect(array) {
    var max = 0;
    for (var i = 0; i < array.length; i++) {
        var bits = array[i];
        for (var j = 0; i + j < array.length;) {
            var row = array[i + j];
            j++;
            var size = 0;
            for (var k = 0; k < row.length; k++) {
                if (!row[k]) bits[k] = 0;
                size = ones[k] ? size + j : 0;
                if (size > max) max = size;
            }
        }
    }
    return max;
}

Tablica jest podzielona na wiersze zgodnie z innymi odpowiedziami, więc każdy możliwy zakres wierszy jest zapętlony. Biorąc pod uwagę zakres rzędów, następnym krokiem jest zmierzenie dostępnych prostokątów. Osiąga się to poprzez ANDing rzędów bitowych; wynikiem jest lista bitów, które zostały ustawione w całym zakresie wierszy. Następnie pozostaje znaleźć maksymalną długość ustawionych bitów w rzędzie i pomnożyć ją przez wysokość zakresu. Test bezwstydnie skradziony z @ ed65:

f=
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

// test cases as strings, converted to 2d arrays
result.textContent = [
  ['0', 0],
  ['1', 1], 
  ['00 00', 0],
  ['01 10', 1],
  ['01 11', 2],
  ['111 010 111', 3],
  ['101 011 111', 4],
  ['0111 1110 1100', 4],
  ['1111111 1110111 1011101', 7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000', 20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110', 12]
].map(t => t[0].replace(/ /g, '\n') + '\n' + t[1] + '\n' + f(t[0].split` `.map(r => [...r]))).join`\n\n`

<pre id=result></pre>

Python 2.7, 93 91 89 81 79 bajtów

f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

Dane wejściowe to lista krotek. Sprawdź mniejsze przypadki testowe tutaj i większe przypadki testowe tutaj .

Bez zapamiętywania dwa ostatnie przypadki testowe przekraczają limit czasu Ideone, ponieważ wymagają one odpowiednio 1530 831 935 i 2 848 806 121 połączeń do f , co zajmuje 39 i 72 minuty na moim komputerze.

Algorytm

Dla danej macierzy M , ogólną ideą jest iteracja po wszystkich podmacierzach M poprzez usunięcie górnych rzędów i obracanie ćwierćobrotów przeciwnie do ruchu wskazówek zegara, śledząc rozmiary napotkanych podmacierzy, które składają się w całości z 1 bitu.

Gra w golfa w bezpośrednią rekurencyjną implementację powyższej idei prowadzi do funkcji f (M), która wykonuje następujące czynności.

1. Jeśli M nie zawiera żadnych 0 bitów, zwróć liczbę 1 bitów.

2. Jeśli obróciliśmy już M dwa razy i nie zawiera on 1 bitu, zwróć 0 .

3. Jeśli obróciliśmy już M pięć razy, zwróć 0 .

4. Rekurencyjnie wzywaj f na M bez górnego rzędu.

5. Wywołanie rekurencyjne f na M obrócone o ćwierć obrotu przeciwnie do ruchu wskazówek zegara.

6. Zwraca maksymalną wartość zwracaną z wywołań rekurencyjnych.

Kod

W implementacji używamy dodatkowego argumentu funkcji t, który domyślnie ma wartość 1, aby śledzić, ile razy już obróciliśmy tę konkretną macierz. Umożliwia to skondensowanie kroków od 1 do 3 w jeden krok poprzez przetestowanie ​`t/3`in`M`​i powrót, ​`M`.count(`t`)​jeśli test się nie powiedzie.

1. Jeśli t = 1 , nie rotowaliśmy tej konkretnej submatrix wcześniej w tej gałęzi.

   t / 3 = 0 , więc ​`t/3`in`M`​zwróci True iff reprezentacja ciągu M zawiera znak 0 .

   Jeśli nie, wracamy ​`M`.count(`t`)​liczba czasach postać 1 pojawi się w ciągu reprezentującego M .

   Zauważ, że macierz bez 0 bitów może wystąpić tylko wtedy, gdy t = 1 , ponieważ nie powtarzamy się w tym przypadku.

2. Jeśli 3 ≤ t ≤ 5 , wcześniej obróciliśmy tę konkretną submatrix co najmniej dwa razy w tej gałęzi.

   t / 3 = 1 , więc ​`t/3`in`M`​zwróci True iff reprezentacja ciągu M zawiera znak 1 .

   Jeśli nie, wracamy 0 obliczana jako ​`M`.count(`t`)​, ile razy reprezentację ciąg t (czyli postać 3 , 4 lub 5 ) pojawia się w ciągu reprezentującego M .

3. Jeśli t = 6 , wcześniej obróciliśmy tę konkretną submatrię pięć razy w tej gałęzi.

   t / 3 = 2 , więc ​`t/3`in`M`​zwróci False , ponieważ reprezentacja ciągu M nie zawiera znaku 2 .

   Wracamy 0 obliczana jako ​`M`.count(`t`)​, ile razy postać 6 pojawi się w ciągu reprezentującego M .

Jeśli f jeszcze nie powrócił, pozostałe kroki są wykonywane.

4. f(M[1:])wywołuje f na M bez górnego rzędu. Ponieważ t nie jest określone, domyślnie przyjmuje wartość 1 , co oznacza, że ​​po raz pierwszy f napotka tę konkretną submatrix w tej gałęzi.

5. f(zip(*M)[::-1],t+1)wywołania f na M obrócone o ćwierć obrotu przeciwnie do ruchu wskazówek zegara, zwiększając t, aby śledzić czas, w którym obróciliśmy tę konkretną submatrix w tej gałęzi.

   Przełom czwarta otrzymuje się skompresowanie rzędy M siebie, powracając krotki odpowiednie elementy M rzędów jest, zatem transpozycji M , a następnie odwrócenie kolejności wierszy (czyli umieszczenie górnego rzędu od dołu i odwrotnie ).

6. Wreszcie maxzwraca maksimum wartości zwrotnych z wywołań rekurencyjnych.

JavaScript (ES6), 154 176

Edit próbował trochę skrócić, ale nie może konkurować z rozwiązaniem @ Neil

Wypróbuj każdy możliwy prostokąt, zwróć maksymalny rozmiar. Prawdopodobnie ten sam algorytm odpowiedzi Matla, tylko 6 razy dłuższy.
Dane wejściowe jako tablica liczb całkowitych 2d

g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

Mniej golfa

Jest to oryginalny algorytm, wersja w golfa nadużywa wielu funkcji przechodzenia przez tablicę zamiast pętli

g=>{
  v = 0
  for(i = h = g.length; i; i--)
    for(j = w = g[0].length; j; j--)
    {
      p = true
      for(k=0; p && k <= h-i; k++)
        for(l=0; p && l <= w-j; j++)
          p = g.slice(k, k+i).some(r=>r.slice(l, l+j).some(x=>!x));
      if (!p && i*j<v)
        v = i*j
    }
  return v
}

Test

f=g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

console.log=(...x)=>O.textContent+=x+'\n'

// test cases as strings, converted to 2d arrays
;[
  ['0',0],['1',1],['00 00',0],['01 10',1],['01 11',2],
  ['111 010 111',3],['101 011 111',4],
  ['0111 1110 1100',4],['1111111 1110111 1011101',7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000',20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110',12]
].forEach(t=>{
  var k=t[1]
  var p=t[0].split` `.map(r=>[...r].map(x=>+x))
  var r=f(p)
  console.log((r==k?'OK':'KO')+' '+r+(r==k?'':' expected '+k)+'\n'+p.join`\n`+'\n')
  })

<pre id=O></pre>

APL (Dyalog Extended) , 27 23 20 bajtów

-3 bajty autorstwa Adama i ngn

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}

Wypróbuj online!

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}    Monadic function taking an argument ⍵:
                 ⍳⍴⍵     Indices: e.g. for a 3x7 array
                                       (1 1) (1 2) ...  (1 7)
                                       (2 1) (2 2)  ... (2 7)
                                       (3 1) (3 2)  ... (3 7)
    (×/×⍵⍷⍨⍴∘1)         Helper fn: Takes ⍵ and x (e.g. (2 2))
            ⍴∘1             Make an array of 1s of shape x. Call it a.
        ⍵⍷⍨                 All places where a exists in x
     ×/                      Product of x's dims (size of a)
       ×                 Size of a where a is in ⍵, and 0 elsewhere.
    (×/×⍵⍷⍨⍴∘1)¨        Call the helper function on x and each (¨) index.
                            We now have a nested list containing sizes of blocks in ⍵
                            and many 0s.
   ∊                        Flatten
 ⌈/                        Find the maximum value.

Brachylog , 20 17 15 bajtów

Dzięki Kroppeb za 2 bajty

{s\sc≡ᵛ¹l}ᶠ⌉|hh

Wypróbuj online!

Wyjaśnienie

{        }ᶠ      Find all possible outputs of the following predicate:
 s                Find a sublist of the array (i.e. remove 0 or more rows from the top
                  and/or bottom)
  \               Transpose the array
   s              Find a sublist again
                  The result is some sub-rectangle of the array
    c             Concatenate all the rows in that rectangle into one list
     ≡ᵛ¹          Verify that all the elements are 1
        l         Get the length (i.e. how many 1's make up the rectangle)
                 Now we have a list of the sizes of all possible 1-rectangles
           ⌉     Take the maximum

            |    If no 1-rectangles could be found:
             hh   Take the head of the head of the array (i.e. the top left element)
                 Since the array contains no 1's in this case, this will give 0

R , 129 122 bajtów

function(M,D=dim(M),L=`for`){L(i,1:D,L(j,1:D[2],L(r,0:(D-i),L(c,0:(D[2]-j),F<-max(F,i*j*(i*j==sum(M[r+1:i,c+1:j])))))))
F}

Wypróbuj online!

Proste i proste podejście z użyciem brutalnej siły.

Rozwinięty kod i objaśnienie:

function(M){                       # M is the matrix of 0/1
n = 0                              # n is the biggest rectangle found
R=nrow(M)
C=ncol(M)
for(i in 1:R)                      # for each possible num of rows of the rectangle
  for(j in 1:C)                    # for each possible num of cols of the rectangle
    for(r in 0:(R-i))              # for each possible position offset on the rows
      for(c in 0:(C-j){            # for each possible position offset on the cols

         subM = M[1:i+r,1:j+c]     # sub-set the matrix given the size of rectangle and offsets

         if(sum(subM)==i*j)        # if sub-matrix is full of 1's
            rec = i*j              # (i.e. nrow*ncol == sum of values in sub-matrix)
         else                      # store the rectangle area
            rec = 0                # otherwise store 0

         n = max(n,rec)            # keep the maximum rectangle found
      }
}

Stax , 14 bajtów

π└ÿ§L▓═J║φ§╦╢9

Uruchom i debuguj

Matlab 106 bajtów

x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

Nie golfowany:

x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

Operacja w pętli rozpoczyna się od splotu 2D conv2()tablicy wejściowej z p*mtablicą jedności. ==p*msprawdza, czy wynikowa tablica zawiera element równy p*m. Odpowiedni element jest odwrócony 1, wszystkie pozostałe elementy są odwrócone 0. any()zamienia tablicę w wektor. Kolumny zawierające co najmniej jeden niezerowy wpis są odwracane 1, w przeciwnym razie 0. p*m*()zwielokrotnia wektor, p*mzamieniając tym samym wszystko w 1-s p*m. [__,r]nawiasy kwadratowe łączą uzyskany wynik z poprzednim maksymalnym obszarem przechowywanym w r. Na koniec max()znajduje maksymalną wartość w wynikowym wektorze.

Matlab (222)(209)

Właściwie to rozwiązanie sprawia mi wstyd z powodu podwójnego rozmiaru rzeczywistego rozwiązania w tym samym języku, ale ... cholera, myślałem o tym przez 6 godzin! sztuczka jest nieco odmienna od odpowiedzi Dennisa i Neila.

    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end

• Funkcja jest wywoływana jako

  y=[1 1 1 0 1 1 0 0 0;
  1 1 0 1 1 1 1 0 0;
  0 0 1 1 1 1 1 1 0;
  0 1 1 1 1 1 1 1 1;
  0 0 1 1 1 1 1 1 0;];
  t=g(y,y,[],0,0,0);t,
  

• Mógłbym zaoszczędzić więcej bajtów, jeśli wprowadzę długość macierzy w wymiarach funkcji, chociaż więcej golfa jest w toku.

• Jak to działa?

  Algorytm ten dodaje do siebie rzeczywistą macierz przesuniętą z niej w lewo, z lekkim kręceniem (&). na dowolnym etapie uzyskana macierz jest ustawiana jako początkowa i dodawana do siebie kilkakrotnie przesuwana w górę, a następnie ponownie uruchamiana od nowa z nową macierzą. Wszystkie podelementy wszystkich macierzy wygenerowanych przez tę operację (original_matrix+shifted_matrix)&shifted_and_original_matrices)są zmaksymalizowane do wyniku.

przykład:

     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0  
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0                             
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4

Japt , 30 bajtów

®åÏ*°X}ÃÕ®£ZãYÄÃm®rm *Zl}Ãc rw

Wypróbuj wszystkie przypadki testowe

Około portu galaretki Dennisa. Przypadki testowe to po prostu tablice liczb 2D, przekonwertowane z formatu pytania za pomocą tego .

Wyjaśnienie:

®      Ã                          #For each row:
 å    }                           # Replace each number with this running total:
    °X                            #  Increment the previous total
  Ï*                              #  Multiply it by the current number
        Õ                         #Transpose rows and columns
         ®               Ã        #For each column:
          £    Ã                  # Iterate over the range [0..length) as Y:
           ZãYÄ                   #  Get the subsections of that column with length Y+1
                m®      }         # For each subsection:
                  rm              #  Get the minimum
                     *Zl          #  Multiply it by the length
                          c       #Flatten everything to a single list of possible rectangle sizes
                            rw    #Get the maximum

J , 38 bajtów

,"0/&(1+i.)/@$>./@,@:((#**/)@,;._3"$)]

Wypróbuj online!

w jaki sposób

,"0/&(1 + i.)/@$ >./@,@:((# * */)@,;._3"$) ]
              @$                             NB. pass the shape of
                                             NB. the input (rows, cols)
                                             NB. to...
,"0/&(1 + i.)/                               NB. this verb, which will
    &(1 + i.)/                               NB. will first create 2
                                             NB. lists: 1...num rows
                                             NB. and 1...num cols.
,"0/                                         NB. and then creat a cross
                                             NB. of every possible 
                                             NB. concatenation of the two,
                                             NB. giving us all possible 
                                             NB. rectangle sizes. pass 
                                             NB. that and...
                                           ] NB. the original input
                 >./@,@:((# * */)@,;._3"$)   NB. to this verb, which
                                   ;._3"$    NB. will take every 
                                             NB. possible rectangle of
                                             NB. every size,
                                 @,          NB. flatten it and...
                         (# * */)            NB. multiply the size of
                                             NB. the list by the list's 
                                             NB. product, yielding the
                                             NB. size of the list if it's
                                             NB. all ones, zero otherwise.
                     ,@:                     NB. Flatten all those results
                                             NB. into one big list
                 >./@                        NB. and take the max.