Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Tích lớn nhất trong lưới

Tìm tích lớn nhất của k số nằm thẳng hàng trong một lưới.

Bạn sẽ học được gì

  • Duyệt lưới theo bốn hướng bằng các cặp bước nhảy
  • Kiểm tra biên trước khi đọc một đoạn
  • Theo dõi giá trị lớn nhất hiện tại

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.