המסלול הכבד ביותר

אדם צריך להגיע ממיקום אחד לאחר. בדרכו הוא יכול לעבור בתחנות. בכל תחנה יש מספר מסוים של משקלי זהב במשקלים שונים שהוא יכול לקחת. הוא רוצה לקחת את המשקל הגדול ביותר של משקלי הזהב האפשרי. אך הוא יכול לעבור מתחנה לתחנה רק לפי תנאים מסוימים שיפורטו להלן.

המשקלים של משקלי הזהב שיש בתחנות מאוחסנים במערך חד-ממדי של מספרים חיוביים ממש (לא אפס). האדם נמצא בתא הראשון במערך והוא מעוניין להגיע אל התא האחרון.

בכל צעד (ספירת הצעדים מתחילה מ-1) הוא יכול לקפוץ קפיצה שעלותה היא הסכום של הערך הנמצא במערך במיקום בו הוא נמצא ומספרו של הצעד.

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

לדוגמה, אם המערך המכיל את משקלי משקלי הזהב הינו:

012345678
212314131

מתחילים בתא 0 לקחת את המשקל שמשקלו 2. בצעד הראשון אפשר ללכת רק ימינה, והקפיצה היא גודל 3 = הסכום של מספר הצעד (1) + הערך בתא (2). מגיעים לתא 3 לקחת את המשקל שמשקלו 3. הקפיצה הבאה האפשרית היא גודל 5 = הסכום של מספר הצעד (2) + הערך בתא (3). לכן אי אפשר לקפוץ שמאלה, אלא רק ימינה ומגיעים לתא 8 שהוא התא האחרון במערך. לוקחים את המשקל שמשקלו 1.

סה"כ המשקל של משקלי הזהב שלקחנו הוא 6 (2+3+1 = 6, בתא 0, בתא 3, ובתא 8).

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

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

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

אילוצים:
  • יש להחזיר את המשקל המקסימלי וגם להדפיס את המסלולים.
  • מותר לשנות את המערך במהלך השיטה, אבל המערך צריך לחזור לקדמותו לאחר ביצוע השיטה.
דוגמה 1:
קלט: 
arr = [9,4,7,7,4,4,1,3,1,2,1,3,2,1,9,2]
פלט: 
1. 0 - 10 - 13 - 9 - 15 sum = 15
2. 0 - 10 - 13 - 9 - 3 - 15 sum = 22
3. 0 - 10 - 7 - 13 - 8 - 2 - 15 sum = 24
4. 0 - 10 - 7 - 1 - 9 - 2 - 15 sum = 28
28

הסבר: המסלול הכבד ביותר הוא המסלול הרביעי עם משקל 28

דוגמה 2:
קלט: 
arr = [2,1,2,3,1,4,1,3,1]
פלט: 
1. 0 - 3 - 8 sum = 6
6

הסבר: קיים מסלול אחד אפשרי עם משקל 6

דוגמה 3:
קלט: 
arr = [1,2,3]
פלט: 
1. 0 - 2 sum = 4
4

הסבר: משקל המסלול הוא סכום הערכים בתאים 0 ו-2

דוגמה 4:
קלט: 
arr = [5,1,1,1,5]
פלט: 
MAX_INT_LANGUAGE

הסבר: אין מסלול אפשרי לתא האחרון

דוגמה 5:
קלט: 
arr = [1,1,1]
פלט: 
1. 0 - 2 sum = 2
2

הסבר: אין מסלול אפשרי לתא האחרון

דוגמה 6:
קלט: 
arr = [3,2,4,1,5]
פלט: 
1. 0 - 4 sum = 8
8

הסבר: משקל המסלול הוא סכום הערכים בתאים 0, 3 ו-4

דוגמה 7:
קלט: 
arr = [1,2]
פלט: 
MAX_INT_LANGUAGE

הסבר: אין מסלול אפשרי לתא האחרון

דוגמה 8:
קלט: 
arr = [2]
פלט: 
1. 0 sum = 2
2

הסבר: מערך באורך 1, המשקל הוא הערך בתא 0

Loading...
נשמרLn 1, Col 1

קלט:

arr = [9,4,7,7,4,4,1,3,1,2,1,3,2,1,9,2]

הפלט המבוקש:

1. 0 - 10 - 13 - 9 - 15 sum = 15
2. 0 - 10 - 13 - 9 - 3 - 15 sum = 22
3. 0 - 10 - 7 - 13 - 8 - 2 - 15 sum = 24
4. 0 - 10 - 7 - 1 - 9 - 2 - 15 sum = 28
28