Đề bài
Gọi một đoạn là k ô liên tiếp nằm trên một đường thẳng: từ trái sang phải theo hàng, từ trên xuống dưới theo cột, hoặc theo một trong hai đường chéo. Nhân các số trong mỗi đoạn và tìm đoạn có tích lớn nhất.
Hãy viết largest_product_in_grid(grid, k).
Đầu vào
grid: Một lưới số hình chữ nhật; mọi hàng có cùng độ dài.
k: Độ dài của một đoạn.
Đầu ra
Trả về tích lớn nhất trên tất cả các đoạn độ dài k. Nếu không có đoạn độ dài k nào nằm vừa trong lưới theo bất kỳ hướng nào, trả về 0.
Ràng buộc
1 ≤ rows, columns ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5
Ví dụ
Đầu vào:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
Kết quả mong đợi:
expected = 72
Đầu vào:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
Kết quả mong đợi:
long long expected = 72;
Đầu vào:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
Kết quả mong đợi:
long expected = 72;
Giải thích
Đoạn tốt nhất là 8 và 9 ở hàng dưới cùng: 8 × 9 = 72. Đường chéo 5, 9 chỉ cho 45.
Đầu vào:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
Kết quả mong đợi:
expected = 504
Đầu vào:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
Kết quả mong đợi:
long long expected = 504;
Đầu vào:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
Kết quả mong đợi:
long expected = 504;
Giải thích
Hàng dưới cùng cho 7 × 8 × 9 = 504, lớn hơn cột bên phải 3 × 6 × 9 = 162 và mọi đường chéo.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chỉ cần bốn hướng: sang phải, xuống dưới, chéo xuống phải và chéo xuống trái. Các hướng còn lại chỉ là những đoạn đó đọc ngược.
Gợi ý 2
Từ mỗi ô bắt đầu, kiểm tra xem ô cuối của đoạn còn nằm trong lưới hay không.
Gợi ý 3
Chỉ trả về 0 khi không có đoạn độ dài k nào vừa trong lưới.
Độ phức tạp mong đợi
thời gian O(rows × cols × k), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.