נתון מערך חד-ממדי a המלא במספרים שלמים. ומספר שלם k. יש למצוא את תת-המערך בגודל k (אינו גדול מגודל המערך) שסכומו הוא המינימלי, ולהדפיס את האינדקסים של תחילת תת-המערך ושל סופו.
לדוגמה, אם המערך a הוא זה:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 4 | 2 | 5 | 6 | 3 | 8 | 1 | 5 | 9 |
k = 3 אז תת-המערך בגודל 3 שסכומו הוא הקטן ביותר הוא זה שמתחיל באינדקס 1 ומסתיים באינדקס 3. הסכום 4 + 2 + 5 הוא הקטן ביותר. ויודפס Minimum sum sub-array is (1,3).k = 2 אז יש שני תת-מערכים בגודל 2 שסכומם הוא הקטן ביותר (6). גם זה שמתחיל באינדקס 1 ומסתיים באינדקס 2, וגם זה שמתחיל באינדקס 7 ומסתיים באינדקס 8. לכן יודפס באופן שרירותי, Minimum sum sub-array is (1,2) או Minimum sum sub-array is (7,8).השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
k אינו גדול מגודל המערך.
arr = [10, 4, 2, 5, 6, 3, 8, 1, 5, 9], k = 3
Minimum sum sub-array is (1,3)
הסבר: תת-המערך שמתחיל באינדקס 1 ומסתיים באינדקס 3 הוא בעל הסכום המינימלי.
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3], k = 4
Minimum sum sub-array is (0,3)
הסבר: תת-המערך שמתחיל באינדקס 0 ומסתיים באינדקס 3 הוא בעל הסכום המינימלי.
arr = [7, 2, 8, 1, 2, 8, 1, 8, 2, 8], k = 3
Minimum sum sub-array is (1,3)
הסבר: תת-המערך שמתחיל באינדקס 1 ומסתיים באינדקס 3 הוא בעל הסכום המינימלי.
arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], k = 5
Minimum sum sub-array is (0,4)
הסבר: כל תת-מערך בגודל 5 הוא בעל סכום זהה.
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100], k = 2
Minimum sum sub-array is (0,1)
הסבר: תת-המערך שמתחיל באינדקס 0 ומסתיים באינדקס 1 הוא בעל הסכום המינימלי.
arr = [5, 4, 3, 2, 1, 0, -1, -2, -3, -4], k = 3
Minimum sum sub-array is (7,9)
הסבר: תת-המערך שמתחיל באינדקס 7 ומסתיים באינדקס 9 הוא בעל הסכום המינימלי.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 5
Minimum sum sub-array is (0,4)
הסבר: תת-המערך שמתחיל באינדקס 0 ומסתיים באינדקס 4 הוא בעל הסכום המינימלי.
קלט:
arr = [10, 4, 2, 5, 6, 3, 8, 1, 5, 9], k = 3
הפלט המבוקש:
Minimum sum sub-array is (1,3)