מסלול מקסימלי במערך דו-ממדי

נתון מערך דו-ממדי mat של מספרים שלמים חיוביים קטנים מ-100.

נגדיר: מסלול חוקי במערך כסדרה של תאים במערך, המתחילה בתא הראשון (שורה 0 ועמודה 0) ומתקדמת לפי ספרת האחדות והעשרות של המספר שבתא במערך. עד לתא האחרון במערך (שורה אחרונה ועמודה אחרונה).

לדוגמה, אם בתא [3][2] נמצא המספר 15, אז אפשר היה להתקדם:

• או 1+ שורות ו- 5+ עמודות, כלומר לתא [4][7]
• או 5+ שורות ו- 1+ עמודות, כלומר תא [8][3]

לכל מסלול יש סכום, שהוא סך הערכים בתאים שהוא עובר בהם, כולל הראשון והאחרון.

יש להחזיר את הסכום המקסימלי שניתן לצבור במסלול תקין במערך. אם אין מסלול כזה יוחזר הערך Integer.MIN_VALUE.

לדוגמה, עבור המערך הבא:

יש להחזיר 86, יש ארבעה מסלולים חוקיים במערך (כתובים להלן) והסכום הגדול ביותר ביניהם הוא זה של המסלול השני (שהוא מסומן במערך):

1. [0, 0] = 12 → [1, 2] = 21 → [3, 3] = 20 → [5, 3] = 1 → [5, 4] = 23 = 77
2. [0, 0] = 12 → [1, 2] = 21 → [2, 4] = 30 → [5, 4] = 23 = 86
3. [0, 0] = 12 → [2, 1] = 23 → [4, 2] = 10 → [5, 2] = 3 → [5, 4] = 23 = 61
4. [0, 0] = 12 → [2, 1] = 23 → [5, 3] = 1 → [5, 4] = 23 = 59

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

mat =
[[12, 22, 23, 54, 11],
 [43, 35, 21, 20, 30],
 [34, 23, 43, 22, 30],
 [25, 31, 2, 20, 34],
 [10, 22, 10, 11, 10],
 [40, 13, 3, 1, 23]]

86

mat =
[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

Integer.MIN_Language

mat =
[[10, 10, 2],
 [10, 10, 2],
 [2, 2, 2]]

24

mat =
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

5