Maximum Sum Subarray of Size K
ניתן לך מערך של מספרים שלמים nums ואורך חלון k. בחן כל רצף של בדיוק k איברים סמוכים והחזר את הסכום הגדול ביותר מביניהם. הערכים יכולים להיות שליליים, ולכן גם התשובה יכולה להיות שלילית.
פונקציה
- numsinteger-array
- מערך המספרים השלמים
- kinteger
- כמה איברים סמוכים מכילה כל חלונית
- מחזירהinteger
- הסכום הגדול ביותר של כל k איברים עוקבים
אילוצים
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104
דוגמאות
- קלט
- nums = [4, -1, 3, 7, -2, 5, 1]k = 3
- פלט
- 10
- הסבר
- סכומן של חמשת החלונות באורך 3 הוא
6,9,8,10ו-4. הסכום הגדול ביותר הוא7 + (-2) + 5 = 10.
- קלט
- nums = [-3, -8, -1, -6]k = 2
- פלט
- -7
- הסבר
- כל הערכים שליליים, ולכן גם כל סכומי החלונות שליליים:
-11,-9ו--7. הגדול מביניהם הוא-1 + (-6) = -7.
- קלט
- nums = [5, -2, 4]k = 3
- פלט
- 7
- הסבר
- כאשר
kשווה לאורך המערך, יש חלון אחד — המערך כולו — ו-5 + (-2) + 4 = 7.
+15 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל גם להחזיר את המקום שבו החלון הטוב ביותר מתחיל, ולבחור את החלון השמאלי ביותר במקרה של שוויון?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כתבו את הסכומים של שני חלונות סמוכים, למשל זה שמתחיל באינדקס 0 וזה שמתחיל באינדקס 1. מה משותף להם?
יש להם
k-1איברים משותפים. הזזת החלון צעד אחד ימינה מוסיפה איבר חדש ומסירה איבר ישן אחד, ולכן הסכום החדש מתקבל מהסכום הישן בשתי פעולות.חבר פעם אחת את
kהאיברים הראשונים. לאחר מכן, עבור כלiמ־kועד הסוף, הוסף אתnums[i], החסר אתnums[i-k], ושמור את הסכום הגדול ביותר שראית.
פתרון
יש n-k+1 חלונות, וחישוב כל אחד מהם מחדש דורש k פעולות חיבור. הטריק הוא ששני חלונות סמוכים חופפים בכל האיברים פרט לשניים. החליקו את החלון במקום לבנות אותו מחדש: ערך אחד נכנס, ערך אחד יוצא, וכל סכום של חלון דורש שתי פעולות.
חברו את כל החלונות
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
חלון נקבע לפי המקום שבו הוא מתחיל. הוא יכול להתחיל באינדקס 0, 1 וכן הלאה עד n-k, כי התחלה מאוחרת יותר תחרוג מסוף המערך. עבור כל נקודת התחלה, מחברים את k האיברים ומשווים את הסכום לתוצאה הטובה ביותר עד כה.
עבור [4, -1, 3, 7, -2, 5, 1] ו-k = 3 מתקבלים הסכומים 6, 9, 8, 10, 4, והתשובה היא 10. מאתחלים את התוצאה הטובה ביותר לסכום של החלון הראשון, או למספר השלם הקטן ביותר, ולעולם לא ל-0: כשכל הערכים שליליים, 0 יהיה גדול מכל חלון אמיתי.
העלות היא (n-k+1) × k פעולות חיבור. היא מגיעה לשיאה כאשר k הוא בערך מחצית מ-n: כאשר n = 10^4 ו-k = 5000, מדובר ב-5001 × 5000, כלומר בערך 2.5 × 10^7 פעולות חיבור, וכמעט כולן חוזרות על עבודה שכבר נעשתה עבור החלון הקודם.
אלגוריתם
- הגדר את
bestלערך הקטן ביותר האפשרי. - עבור כל התחלה מ־
0עדn-k, הגדרtotal = 0. - הוסף אל
totalאת הערכים מ־nums[start]ועדnums[start+k-1]. - אם
totalגדול מ־best, שמור אותו. - החזר את
best.
def maxSumSubarray(nums, k):
n = len(nums)
best = None
for start in range(n - k + 1):
total = 0
for i in range(start, start + k):
total += nums[i]
if best is None or total > best:
best = total
return bestהזז חלון קבוע
האינטואיציה
השווה בין החלון שמתחיל באינדקס 0 לבין זה שמתחיל באינדקס 1. ב־[4, -1, 3, 7, -2, 5, 1] כאשר k = 3, הסכומים שלהם הם 4 + (-1) + 3 = 6 ו־(-1) + 3 + 7 = 9. שניהם כוללים את -1 ואת 3. הסכום השני הוא הסכום הראשון ועוד הערך שנכנס, 7, פחות הערך שיצא, 4: 6 + 7 - 4 = 9.
כך קורה בכל צעד. כשקצהו הימני של החלון זז לאינדקס i, האיבר באינדקס i נכנס והאיבר באינדקס i-k יוצא. לכן מחברים פעם אחת את איברי החלון הראשון, ואז מעדכנים את הסכום באמצעות חיבור אחד וחיסור אחד בכל צעד. הסכומים הם 6, 9, 8, 10, 4, בדיוק כמו בחישוב בכוח גס, ושומרים את הגדול ביותר.
כל איבר נכנס פעם אחת ויוצא לכל היותר פעם אחת, ולכן זמן הריצה הוא O(n). שומרים שני מספרים, סכום החלון הנוכחי והסכום הטוב ביותר, ולכן המקום הנוסף הוא O(1). אף סכום כאן אינו עולה על 10^4 × 10^4 = 10^8, ולכן מספר שלם בן 32 סיביות מספיק.
אלגוריתם
- חברו את
nums[0]עדnums[k-1]לתוךwindow. - הגדירו
best = window. - עבור כל
iמ־kעדn-1, הוסיפו אתnums[i]והחסירו אתnums[i-k]. - אחרי כל שלב, הגדירו את
bestלערך הגדול יותר מביןbestו־window. - החזירו את
best.
def maxSumSubarray(nums, k):
# Sum of the first window, nums[0..k-1].
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
# Slide one step right: nums[i] enters, nums[i-k] leaves.
window += nums[i] - nums[i - k]
best = max(best, window)
return best
מלכודות ומקרי קצה
הרעיון של החלון פשוט, ולכן הבאגים מסתתרים בערכי ההתחלה ובאינדקסים.
- התחלת
bestב-0. עם[-3, -8, -1, -6]ו-k = 2, התשובה האמיתית היא-7, אבל עלbestשערכו0אי אפשר להתגבר, ולכן הוא מוחזר כתשובה. - החסרת האיבר הלא נכון. כש-
nums[i]נכנס, האיבר שיוצא הואnums[i-k]. שימוש ב-nums[i-k+1]או ב-nums[i-k-1]יוצר חלונות באורך שגוי. - עצירה מוקדמת מדי של חיפוש הכוח הגס. החלון האחרון מתחיל ב-
n-k, ולכן הלולאה חייבת לכלול אותו. כש-k = n, זהו החלון היחיד, ושגיאת off-by-one לא בודקת אף חלון ומחזירה את ערך ההתחלה שלbest. - השוואה רק אחרי הלולאה. החלון הטוב ביותר יכול להיות הראשון, לכן יש להשוות גם את הסכום הראשון, או לאתחל את
bestבערכו. - שוכחים שב-R וב-Lua הספירה מתחילה ב-1. החלון הראשון הוא
nums[1..k], והאיבר שיוצא כש-nums[i]נכנס הוא עדייןnums[i-k].
שאלות נפוצות4
מהו חלון הזזה בגודל קבוע?
זהו טווח של בדיוק k איברים סמוכים, שנע צעד אחד בכל פעם לאורך מערך. במקום לחשב מחדש את הטווח מההתחלה בכל מיקום, מעדכנים ערך מצטבר: מוסיפים את האיבר שנכנס מימין ומסירים את זה שיוצא משמאל. כך הופכים עבודה של O(n·k) לעבודה של O(n).
מהי סיבוכיות הזמן של תת־המערך שסכומו מרבי בגודל k?
בשיטת חלון הזזה, זמן הריצה הוא O(n) ונדרשת תוספת של O(1) מקום: מעבר אחד לסכימת החלון הראשון, ואז חיבור אחד וחיסור אחד בכל צעד. חישוב הסכום של כל חלון בנפרד דורש (n-k+1) × k פעולות חיבור, כלומר O(n·k), בערך 2.5 × 10^7 עבור n = 10^4 ו-k = 5000.
במה זה שונה מבעיית תת-המערך המקסימלי?
כאן האורך קבוע ושווה ל־k, ולכן כל מועמד הוא חלון וסכום נע מכסה את כולם. בבעיית תת־המערך המקסימלי האורך אינו קבוע, וצריך להשתמש באלגוריתם של Kadane, שמחליט בכל איבר אם להאריך את הרצף הנוכחי או להתחיל רצף חדש. חלון קבוע אינו מאפשר את הבחירה הזאת.
האם גם סכומי קידומת יכולים לפתור את זה?
כן. בנה את prefix[i] כסכום של i האיברים הראשונים, והחלון שמתחיל ב־s מסתכם ב־prefix[s+k] - prefix[s]. גם זה לוקח זמן O(n), אבל הוא מאחסן n+1 סכומים. חלון ההזזה מחשב את אותם הסכומים באמצעות שני משתנים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def maxSumSubarray(nums, k):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [4, -1, 3, 7, -2, 5, 1] k = 3
צפוי
10