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
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.
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.