רצף k אפסים ארוך ביותר

נתון מערך חד-ממדי a שמכיל רק אפסים (0) ואחדים (1). ומספר שלם אי-שלילי k, יש להחזיר את האורך של התת-סדרה הרציפה הארוכה ביותר של המערך a, שכוללת לכל היותר k אפסים.

לדוגמה, אם נתון המערך a הבא:

01234567891011
110110111100
  • עבור k = 0 יוחזר 4 (הסדרה באורך 4 המתחילה ממקום 6 היא הארוכה ביותר עם 0 אפסים).
  • עבור k = 1 יוחזר 7 (הסדרה באורך 7 המתחילה ממקום 3 היא הארוכה ביותר עם 1 אפסים).
  • עבור k = 2 יוחזר 10 (הסדרה באורך 10 המתחילה ממקום 0 מכילה בדיוק 2 אפסים).
  • עבור k = 3 יוחזר 11 (הסדרה באורך 11 המתחילה ממקום 0 מכילה מספר אפסים מקסימלי אפשרי).
  • עבור k = 4 (וכל המספרים שגדולים מ-4) יוחזר 12 (הסדרה באורך 12 המתחילה ממקום 0 מכילה מספר אפסים מקסימלי אפשרי 4 אפסים, והיא בעצם המערך כולו).

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

דוגמה 1:
קלט: 
a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 0
פלט: 
4

הסבר: הסדרה הארוכה ביותר ללא אפסים היא באורך 4 ומתחילה ממקום 6.

דוגמה 2:
קלט: 
a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 1
פלט: 
7

הסבר: הסדרה הארוכה ביותר עם אפס אחד היא באורך 7 ומתחילה ממקום 3.

דוגמה 3:
קלט: 
a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 2
פלט: 
10

הסבר: הסדרה הארוכה ביותר עם שני אפסים היא באורך 10 ומתחילה ממקום 0.

דוגמה 4:
קלט: 
a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 3
פלט: 
11

הסבר: הסדרה הארוכה ביותר עם שלושה אפסים היא באורך 11 ומתחילה ממקום 0.

דוגמה 5:
קלט: 
a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 4
פלט: 
12

הסבר: הסדרה הארוכה ביותר עם ארבעה אפסים היא באורך 12 ומתחילה ממקום 0.

דוגמה 6:
קלט: 
a = [0, 0, 0, 0, 0],
k = 2
פלט: 
2

הסבר: הסדרה הארוכה ביותר עם שני אפסים היא באורך 2.

דוגמה 7:
קלט: 
a = [1, 1, 1, 1, 1],
k = 0
פלט: 
5

הסבר: הסדרה הארוכה ביותר ללא אפסים היא באורך 5.

דוגמה 8:
קלט: 
a = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
k = 5
פלט: 
10

הסבר: הסדרה הארוכה ביותר עם חמישה אפסים היא באורך 10.

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

קלט:

a = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0],
k = 0

הפלט המבוקש:

4