נתון מערך של מספרים שונים זה מזה, והמשימה היא למצוא את האורך של הרצף הארוך ביותר שניתן ליצור מהמספרים במערך.
לדוגמא –
A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A) = 4 ([2,3,4,5])
להמשיך לקרוא "הרצף הארוך ביותר"נתון מערך של מספרים שונים זה מזה, והמשימה היא למצוא את האורך של הרצף הארוך ביותר שניתן ליצור מהמספרים במערך.
לדוגמא –
A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A) = 4 ([2,3,4,5])
להמשיך לקרוא "הרצף הארוך ביותר"אוקי, אז השאלה היא כזו –
נתון מערך של מספרים ומספר כלשהו k.
צריך לכתוב אלגוריתם שמוצא את הרצף הכי ארוך במערך שיש בו בדיוק k מספרים שונים זה מזה נתון לי ש-k<=n.
קודם כל להיות בטוח שאני סגורה על השאלה.
צריך למצוא את הרצף הכי ארוך שיש בו k מספרים שונים – זאת אומרת שאם k=1, צריך למצוא את הרצף הכי ארוך של מספר מסוים שחוזר על עצמו. אם k=2 צריך למצוא את הרצף הכי ארוך של שני מספרים שחוזרים על עצמם וכן הלאה.
נתונה סדרה ארוכה לא ממוינת של מספרים שלמים.
ידוע שכל איבר בסדרה נמצא לכל היותר במרחק 1000 מקומות ממיקומו הנכון בסדרה לו הייתה ממויינת.
המשימה היא לכתוב אלגוריתם שימיין את הסדרה באופן יעיל, וישתמש בכמות זיכרון קבועה.
להמשיך לקרוא "מערך כמעט ממויין"