נתון מערך לא ממוין A בגודל n, כאשר כל איברי המערך הם מספרים טבעיים.
נגדיר רצף עוקב כרצף של מספרים שלמים מהצורה
x,x+1,x+2,…,x+k
כך שכל האיברים ברצף מופיעים במערך A, לאו דווקא ברצף אינדקסים.
מטרת השאלה היא למצוא את אורך הרצף העוקב הארוך ביותר המופיע במערך.
לדוגמה, עבור המערך: A=(100,4,200,1,3,2) הרצף העוקב הארוך ביותר הוא 1,2,3,4.
סעיף א' (5 נקודות)
הציעו אלגוריתם המקבל מערך A לא ממוין מאורך n של מספרים טבעיים ומוצא את אורך הרצף העוקב הארוך ביותר הרץ בזמן O(nlogn).
סעיף ב' (5 נקודות)
הציעו מבנה נתונים שיאפשר ליישם את הפונקציות הבאות בתוחלת זמן O(1).
פונקציית עוקב: הפונקציה מקבלת אינדקס i ומחזירה אמת אם האיבר A[i]+1 מופיע במערך, ושקר אחרת.
פונקציית קודם: פונקציה מקבלת אינדקס i ומחזירה אמת אם האיבר A[i]−1 מופיע במערך, ושקר אחרת.
סעיף ג' (15 נקודות)
הציעו אלגוריתם המקבל מערך A לא ממוין מאורך n של מספרים טבעיים ומוצא את אורך הרצף העוקב הארוך ביותר הרץ בתוחלת זמן O(n).
נתחו את סיבוכיות הזמן של האלגוריתם שהצעתם.