הרצף הארוך ביותר

נתון מערך של מספרים שונים זה מזה, והמשימה היא למצוא את האורך של הרצף הארוך ביותר שניתן ליצור מהמספרים במערך.
לדוגמא –

A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A) = 4 ([2,3,4,5])

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

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

אני אכתוב את האלגוריתם הזה – 

def longest_subsequence_length(A):
	longest_length = 0
	for n in A:
		current_seq = [n]
		for m in A:
			if m == current_seq[0] - 1:
				current_seq = [m] + current_seq
			if m == current_seq[-1] + 1:
				current_seq.append(m)
		longest_length = max(longest_length, len(current_seq))
	return longest_length

אני אריץ דוגמא על האלגוריתם הנאיבי שלי לראות אם הוא עובד –

A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A): longest_length = 0 n = 2 current_seq = [2] m = 2 m = 5 m = 3 current_seq = [2, 3] m = 10 m = 9 m = 4 current_seq = [2, 3, 4]

אבוי, זה לא עבד, מכיוון שהגעתי ל-4 רק בסוף אז 5 לא נכנס לרצף של [2,3,4] למרות שהוא אמור להיות חלק ממנו.

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

A = [2, 5, 3, 10, 9, 4] saw 2 → seq_1 = 2 saw 5 → seq_2 = 5 saw 3 → seq_1 = 2,3 saw 10 → seq_3 = 10 saw 9 → seq_3 = 9,10 saw 4 → seq_1 = 2,3,4, seq_2 = 4,5 → seq_1 = 2,3,4,5, seq_2 = 2,3,4,5

אז מה בעצם עשיתי פה?

1. בכל פעם שנתקלתי במספר חדש שלא מתחבר לרצף קיים יצרתי לו רצף משל עצמו.
2. כשנתקלתי במספר שמצטרף לרצף קיים יחיד, עדכנתי את הרצף היחיד.
3. כשנתקלתי במספר שמצטרף לשני רצפים קיימים עדכנתי את שניהם עם המספר החדש, ואז עדכנתי את שניהם עם המידע אחד של השני.

• לא יכול להיות מצב שבו מספר יצטרף ליותר משני רצפים קיימים כי כל מספר יכול להיות סמוך לשני מספרים בלבד.

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

 def longest_subsequence_length(A):
	longest_length = 0
	seq = dict()
	for n in A:
		if n-1 in seq:
			seq_min = seq[n-1][0]
		else:
			seq_min = n
		if n + 1 in seq:
			seq_max = seq[n+1][1]
		else:
			seq_max = n
		current_seq = (seq_min,seq_max)
		seq[n] = seq[seq_min] = seq[seq_max] = current_seq
		longest_length = max(longest_length, current_seq[1]-current_seq[0] + 1)
	return longest_length

זה כבר נראה הרבה יותר טוב.
כל מספר מכיל בטבלה seq את המינימום והמקסימום של הרצף בו הוא נמצא. 

כשאני מוצאת מספר n שמתחבר לרצף קיים אז n מקבל את המינימום/מקסימום מהרצף אליו הוא מתחבר, ואם הוא מחבר שני רצפים קיימים, אז כל אחד מהם מקבל את המינימום/מקסימום של השני.

אני אריץ דוגמא – 

A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A): longest_length = 0 seq = {} n = 2 current_seq = (2,2) seq = {2:(2,2)} longest_length = 1 n=5 current_seq = (5,5) seq = {2:(2,2),5:(5,5)} n=3 seq_min = seq[2][0] = 2 seq_max = 3 current_seq = (2,3) seq = {2:(2,3),5:(5,5),3:(2,3)} longest_length = 2 n = 10 current_seq = (10,10) seq = {2:(2,3),5:(5,5),3:(2,3),10:(10,10)} n = 9 seq_min = 9 seq_max = seq[10][1] = 10 current_seq = (9,10) seq = {2:(2,3),5:(5,5),3:(2,3),10:(9,10),9:10} n = 4 seq_min = seq[3][0] = 2 seq_max = seq[5][1] = 5 current_seq = (2,5) seq = {2:(2,5),5:(2,5),3:(2,3),10:(9,10),9:10, 4:(2,5)} longest_length = 4 return 4

הידד!
קיבלתי תשובה נכונה והכל נראה די טוב.

אני אנסה לבדוק כמה מקרי קיצון שעלולים להכשיל את האלגוריתם שלי.
מערך ריק?
הלולאה לא תרוץ ויחזור longest_length=0.
מה לגבי מערך באורך 1?
הלולאה תיצור רצף באורך 1 ותחזיר 1.
מערך של מספרים שאין בו אף רצף?
הלולאה תיצור את כל הרצפים באורך 1 ותחזיר 1.

כשאני מסתכלת על הדוגמא אני רואה שכל המספרים שנמצאים באמצע רצף לא מתעדכנים – למשל בדוגמא למעלה אחרי שעדכנתי את הרצף (2,5) המספר 3 המשיך להצביע על הרצף הישן (2,3). האם המצב הזה יכול ליצור בעיה?

נראה שלא. אם 3 היה מינימום או מקסימום ברצף החדש הוא היה מתעדכן, וכיוון שהוא לא מינימום או מקסימום, אז לא יהיה מצב שבו מספר חדש ירצה להתחבר אליו ויקבל מידע לא נכון.

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

 def longest_subsequence_length(A):
	longest_length = 0
	seq = dict()
	for n in A:
		if n-1 in seq:
			seq_min = seq.pop(n-1)[0]
		else:
			seq_min = n
		if n + 1 in seq:
			seq_max = seq.pop(n+1)[1]
		else:
			seq_max = n
		current_seq = (seq_min,seq_max)
		seq[seq_min] = seq[seq_max] = current_seq
		longest_length = max(longest_length, current_seq[1]-current_seq[0] + 1)
	return longest_length

עכשיו הדוגמא שלי תיראה כך – 

A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A): longest_length = 0 seq = {} n = 2 current_seq = (2,2) seq = {2:(2,2)} longest_length = 1 n=5 current_seq = (5,5) seq = {2:(2,2),5:(5,5)} n=3 seq_min = seq[2][0] = 2 seq_max = 3 current_seq = (2,3) seq = {2:(2,3),5:(5,5),3:(2,3)} longest_length = 2 n = 10 current_seq = (10,10) seq = {2:(2,3),5:(5,5),3:(2,3),10:(10,10)} n = 9 seq_min = 9 seq_max = seq[10][1] = 10 current_seq = (9,10) seq = {2:(2,3),5:(5,5),3:(2,3),10:(9,10),9:10} n = 4 seq_min = seq[3][0] = 2 seq_max = seq[5][1] = 5 current_seq = (2,5) seq = {2:(2,5),5:(2,5),10:(9,10),9:10} longest_length = 4 return 4

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

נושא אחרון חביב, סיבוכיות.

סיבוכיות הזמן של האלגוריתם הזה היא לינארית – אני עוברת על כל איבר במערך פעם אחת ועושה סט סופי של פעולות. סה”כ (O(N. 

מה לגבי סיבוכיות מקום? במקרה הכי גרוע שבו אין אף רצף במערך גודל הטבלה שלי הוא N. במקרה שבו יש רצפים חלק מהמספרים יזרקו והטבלה תהיה גדולה יותר. סה”כ גם כאן הסיבוכיות היא (O(N.

ווהו, אני יכולה ללכת לכתוב את הקוד שלי!

קוד, כרגיל, בגיט – https://github.com/mgershovitz/maya_solves/blob/master/longest_sub_sequence_length.py