โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ผลคูณที่มากที่สุดในตาราง

หาผลคูณที่มากที่สุดของตัวเลข k ตัวที่เรียงกันเป็นเส้นตรงในตาราง

สิ่งที่คุณจะได้เรียนรู้

  • เดินในตารางสี่ทิศทางด้วยคู่ระยะก้าว
  • ตรวจขอบเขตก่อนอ่านค่าในแนว
  • ติดตามค่าสูงสุดระหว่างทาง

โจทย์

ให้เรียกช่อง k ช่องที่เรียงต่อกันเป็นเส้นตรงว่า "แนว" ซึ่งอาจเรียงจากซ้ายไปขวาตามแถว จากบนลงล่างตามคอลัมน์ หรือตามแนวทแยงทั้งสองทิศ ให้คูณตัวเลขในแต่ละแนวแล้วหาแนวที่ให้ผลคูณมากที่สุด

จงเขียนฟังก์ชัน largest_product_in_grid(grid, k)

อินพุต

grid: ตารางตัวเลขรูปสี่เหลี่ยมผืนผ้า ทุกแถวมีความยาวเท่ากัน

k: ความยาวของแนว

เอาต์พุต

คืนค่าผลคูณที่มากที่สุดจากทุกแนวที่ยาว k ช่อง ถ้าไม่มีแนวยาว k ช่องที่วางลงในตารางได้เลยไม่ว่าทิศทางใด ให้คืนค่า 0

เงื่อนไข

1 ≤ จำนวนแถว, จำนวนคอลัมน์ ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 2

ผลลัพธ์ที่คาดหวัง:
expected = 72
อินพุต:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 2;

ผลลัพธ์ที่คาดหวัง:
long long expected = 72;
อินพุต:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

ผลลัพธ์ที่คาดหวัง:
long expected = 72;

คำอธิบาย

แนวที่ดีที่สุดคือ 8 และ 9 ในแถวล่างสุด ได้ 8 × 9 = 72 ส่วนแนวทแยง 5, 9 ได้เพียง 45

ตัวอย่างที่ 2
อินพุต:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 3

ผลลัพธ์ที่คาดหวัง:
expected = 504
อินพุต:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 3;

ผลลัพธ์ที่คาดหวัง:
long long expected = 504;
อินพุต:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

ผลลัพธ์ที่คาดหวัง:
long expected = 504;

คำอธิบาย

แถวล่างสุดให้ 7 × 8 × 9 = 504 ซึ่งมากกว่าคอลัมน์ขวาสุด 3 × 6 × 9 = 162 และมากกว่าแนวทแยงทุกแนว

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ใช้แค่สี่ทิศทางก็พอ ได้แก่ ขวา ลง ทแยงลงขวา และทแยงลงซ้าย ทิศอื่นเป็นแนวเดิมที่อ่านย้อนกลับ

คำใบ้ 2

จากช่องเริ่มต้นแต่ละช่อง ให้ตรวจว่าช่องสุดท้ายของแนวยังอยู่ในตาราง

คำใบ้ 3

คืนค่า 0 เฉพาะเมื่อไม่มีแนวยาว k ช่องที่วางในตารางได้เลย

ความซับซ้อนที่คาดหวัง

เวลา O(rows × cols × k), หน่วยความจำเพิ่ม O(1)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก