מציאת אינדקס להפרש מקסימלי בין ממוצעים

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

החלק השמאלי כולל את כל האיברים מתחילת המערך (אינדקס 0) עד i (כולל)
החלק הימני כולל את כל האיברים מאינדקס i+1 ועד לסוף המערך (אינדקס arr.length-1)

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

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

0	1	2	3
5	7	-2	10

החלוקות האפשריות הן:

i=0 החלק השמאלי הוא {5} והממוצע שלו 5, והחלק הימני הוא {7, -2, 10} והממוצע שלו (7+(-2)+10)/3 = 5. ההפרש הוא 5-5=0
i=1 החלק השמאלי הוא {5, 7} והממוצע שלו (5+7)/2 = 6, והחלק הימני הוא {-2, 10} והממוצע שלו ((-2)+10)/2 = 4. ההפרש הוא 6-4=2
i=2 החלק השמאלי הוא {5, 7, -2} והממוצע שלו (5+7+(-2))/3 = 3.3333, החלק הימני הוא {10} והממוצע שלו 10. ההפרש הוא 10-3.333=6.666

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

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

אילוצים:

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

דוגמה 1:

קלט:

arr = [5, 7, -2, 10]

פלט:

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

דוגמה 2:

קלט:

arr = [1, 1, 1, 1, 1]

פלט:

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

דוגמה 3:

קלט:

arr = [5, 5, 5, 5, 5]

פלט:

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

דוגמה 4:

קלט:

arr = [1, 2]

פלט:

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

דוגמה 5:

קלט:

arr = [3, 1, 4, 1, 5, 9]

פלט:

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

נשמרLn 1, Col 1

קלט:

arr = [5, 7, -2, 10]

הפלט המבוקש: