Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Größtes Produkt in einem Gitter

Finde das größte Produkt von k Zahlen, die in einem Gitter auf einer geraden Linie liegen.

Das lernst du

  • Ein Gitter mit Schrittpaaren in vier Richtungen durchlaufen
  • Vor dem Auslesen einer Reihe die Grenzen prüfen
  • Ein laufendes Maximum mitführen

Problem

Eine Reihe besteht aus k Feldern auf einer geraden Linie: von links nach rechts in einer Zeile, von oben nach unten in einer Spalte oder entlang einer der beiden Diagonalen. Multipliziere die Zahlen einer Reihe und finde die Reihe mit dem größten Produkt.

Implementiere largest_product_in_grid(grid, k).

Eingabe

grid: Ein rechteckiges Zahlengitter, alle Zeilen sind gleich lang.

k: Die Länge einer Reihe.

Ausgabe

Gib das größte Produkt über alle Reihen der Länge k zurück. Passt in keiner Richtung eine Reihe der Länge k ins Gitter, gib 0 zurück.

Einschränkungen

1 ≤ Zeilen, Spalten ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5

Beispiele

Beispiel 1
Eingabe:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 2

Erwartete Ausgabe:
expected = 72
Eingabe:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 2;

Erwartete Ausgabe:
long long expected = 72;
Eingabe:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

Erwartete Ausgabe:
long expected = 72;

Erläuterung

Die beste Reihe ist 8 und 9 in der untersten Zeile: 8 × 9 = 72. Die Diagonale 5, 9 ergibt nur 45.

Beispiel 2
Eingabe:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 3

Erwartete Ausgabe:
expected = 504
Eingabe:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 3;

Erwartete Ausgabe:
long long expected = 504;
Eingabe:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

Erwartete Ausgabe:
long expected = 504;

Erläuterung

Die unterste Zeile ergibt 7 × 8 × 9 = 504, mehr als die rechte Spalte mit 3 × 6 × 9 = 162 oder jede Diagonale.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Vier Richtungen genügen: rechts, unten, rechts unten und links unten. Die übrigen liefern dieselben Reihen nur rückwärts.

Hinweis 2

Prüfe von jedem Startfeld aus, ob das letzte Feld der Reihe noch im Gitter liegt.

Hinweis 3

Gib nur dann 0 zurück, wenn überhaupt keine Reihe der Länge k hineinpasst.

Erwartete Komplexität

Zeit O(rows × cols × k), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.