שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2022 - מערכים

נתון מערך חד ממדי a הממלא במספרים שלמים חיוביים ושליליים ללא אפס! (אין צורך לבדוק זאת). המערך אינו ממוין! כתבו שיטה סטטית longestSubarray המקבלת את המערך כפרמטר ומחזירה את אורכו של התת-מערך (הרציף) הארוך ביותר שכל איבריו הם לסירוגין מספר חיובי ומספר שלילי. השיטה צריכה גם להדפיס מה האינדקס ההתחלתי ומה האינדקס הסופי של התת-מערך המבוקש. אם יש במערך יותר מתת-מערך אחד באורך מקסימלי, יודפסו האינדקסים של התת-מערך הראשון מביניהם. לדוגמא: - עבור המערך {-1, 1, -1, -5, 2, 2} השיטה תחזיר 3 (האיברים של התת-מערך הזה מודגשים) ותדפיס משהו כעין זה: Starting index = 0 Ending index = 2 - עבור המערך {3, 3, 2, -7, 2, 1, 1, -2, -2} השיטה תחזיר 3 ותדפיס משהו כעין זה: Starting index = 2 Ending index = 4 - עבור המערך {1, 2, 3, 4, 5, 4} השיטה תחזיר 1 (אין תת-מערך באורך גדול מ- 1 שיש בו איברים מתחלפים. לכן כל אחד מהאיברים במערך הוא תת-מערך באורך 1) ותדפיס משהו כעין זה: Starting index = 0 Ending index = 0 - עבור המערך {1, -2, 3, -4, -5, 4, 2, -4, 6, -2} השיטה תחזיר 4 (יש שני תת-מערכים באורך 4, אחד מאינדקס 0 עד אינדקס 3, והשני מאינדקס 6 עד אינדקס 9) ותדפיס משהו כעין זה: Starting index = 0 Ending index = 3 חתימת השיטה היא: ```java public static int longestSubarray(int[] a) ``` מה סיבוכיות זמן הריצה והמקום של השיטה שכתבתם? הסבירו תשובתכם. שימו לב: השיטה שתכתבו צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. תשובה שאינה יעילה מספיק כלומר, שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה תקבל מעט נקודות בלבד. אל תשכחו לתעד את מה שכתבתם!

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

פתרון: **מעבר יחיד** על המערך ($O(n)$ זמן, $O(1)$ מקום): ```java public static int longestSubarray(int[] a) { int maxLen = 1, maxStart = 0; int curLen = 1, curStart = 0; for (int i = 1; i < a.length; i++) { // בדיקה אם הסימנים מתחלפים if ((a[i] > 0 && a[i-1] < 0) || (a[i] < 0 && a[i-1] > 0)) { curLen++; } else { // הרצף נשבר - בדיקה אם מצאנו מקסימום חדש if (curLen > maxLen) { maxLen = curLen; maxStart = curStart; } curLen = 1; curStart = i; } } // בדיקה אחרונה אחרי סוף הלולאה if (curLen > maxLen) { maxLen = curLen; maxStart = curStart; } System.out.println("Starting index = " + maxStart + " Ending index = " + (maxStart + maxLen - 1)); return maxLen; } ``` **סיבוכיות זמן**: $O(n)$ - מעבר יחיד על המערך. **סיבוכיות מקום**: $O(1)$ - מספר קבוע של משתנים בלבד.