Maximum Product Subarray
כפול את איברי תת־מערך של nums זה בזה, והחזר את המכפלה הגדולה ביותר שתת־מערך כלשהו יכול להניב. תת־מערך כולל איברים עוקבים ללא פערים, ולעולם אינו ריק, לכן גם למערך של מספרים שליליים יש תשובה. מותר להשתמש באפסים ובערכים שליליים.
פונקציה
- numsinteger-array
- המספרים השלמים שיש להכפיל, שכל אחד מהם בין -10 ל-10
- מחזירהinteger
- המכפלה הגדולה ביותר של תת־מערך שאינו ריק
אילוצים
1 ≤ nums.length ≤ 2 × 104-10 ≤ nums[i] ≤ 10- המכפלה של כל תת־מערך מתאימה למספר שלם חתום בן 32 סיביות.
דוגמאות
- קלט
- nums = [2, -5, 3, -2, 0, 4]
- פלט
- 60
- הסבר
- שני השליליים מבטלים זה את זה:
2 × -5 × 3 × -2 = 60. ה־0 מחלק את המערך לשניים, וה־4 שבצד השני לא יכול לגבור על 60.
- קלט
- nums = [-2, 3, -4, -1]
- פלט
- 24
- הסבר
- המכפלה של כל המערך היא -24, כי הוא מכיל שלושה מספרים שליליים. השמטת האיבר האחרון משאירה שניים מהם:
-2 × 3 × -4 = 24, וזה גדול מ-12 שמתקבלים כשמשמיטים את האיבר הראשון.
- קלט
- nums = [-6, 0, -7]
- פלט
- 0
- הסבר
- תת־מערך שאינו כולל את 0 הוא מספר שלילי יחיד, ותת־מערך שכולל את 0 נותן מכפלה של 0. הבחירה הטובה ביותר היא תת־המערך
[0].
שאלת המשך
איך תדווח גם היכן מתחיל ומסתיים תת־המערך הטוב ביותר, ועדיין בזמן O(n) ובשטח O(1)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
בחישובי סכום, כדאי להשליך סכום מצטבר שיורד מתחת לאפס. בחישובי מכפלה, מכפלה שלילית מאוד יכולה להפוך לגדולה ביותר ברגע שמגיע מספר שלילי נוסף. מה כדאי לזכור מלבד המכפלה הגדולה ביותר עד כה?
התבוננו בתת-המערכים שמסתיימים באינדקס הנוכחי. המכפלה הגדולה ביותר ביניהם היא המספר הנוכחי לבדו, או המספר כפול המכפלה הגדולה ביותר שהסתיימה צעד אחד קודם, או המספר כפול המכפלה הקטנה ביותר שהסתיימה צעד אחד קודם.
עבור על המערך תוך שמירה על
highו־low, המכפלות הגדולה והקטנה ביותר של תת־מערך המסתיים באינדקס הנוכחי. עבור כל מספר חדש, חשב תחילה את שתי המכפלות האפשריות מהערכים הישנים, ואז עדכן את הזוג, וזכור את ערךhighהטוב ביותר שראית.
פתרון
כפל במספר שלילי הופך את סדר המכפלות, ולכן המכפלה הקטנה ביותר עד כה יכולה להפוך לגדולה ביותר בצעד הבא, ואפס מאפס את כל המכפלות. שמרו שני ערכים בכל אינדקס במקום אחד: המכפלה הגדולה ביותר והמכפלה הקטנה ביותר של תת־מערך שמסתיים שם, ומעבר אחד מספיק.
הכפל כל תת־מערך מכל נקודת התחלה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
קבעו אינדקס התחלה והזיזו את אינדקס הסיום ימינה, תוך הכפלת product המצטבר בכל איבר חדש. השוואתו לערך הטוב ביותר אחרי כל צעד מכסה כל תת־מערך פעם אחת. התחילו את best ב־nums[0], כי התשובה יכולה להיות שלילית.
יש בערך n²/2 זוגות של אינדקסי התחלה וסיום, עם כפל אחד בכל זוג: 2 × 10^8 עבור 20,000 איברים.
אלגוריתם
- הגדר את
bestלערךnums[0]. - עבור כל
start, הגדר אתproductל־1. - העבר את
endמ־startעד לאינדקס האחרון, וכפול אתproductב־nums[end]. - אם
productגדול מ־best, שמור אותו. - החזר את
best.
def maxProduct(nums):
n = len(nums)
best = nums[0]
for start in range(n):
product = 1
for end in range(start, n):
# product is now the product of nums[start..end]
product *= nums[end]
if product > best:
best = product
return bestסריקה משני הקצוות, תוך התחלה מחדש באפסים
האינטואיציה
אפסים מחלקים את המערך לרצפים שאין בהם אפסים. בתוך רצף, הערך המוחלט של כל ערך הוא לפחות 1, ולכן למכפלה המוחלטת של תת-מערך ארוך יותר לעולם אין ערך קטן יותר; רק הסימן משתנה. כשיש מספר זוגי של מספרים שליליים, הרצף כולו הוא האפשרות הטובה ביותר. כשיש מספר אי-זוגי, צריך להסיר מספר שלילי אחד, והחיתוך הטוב ביותר מסיר את המספר השלילי הראשון ואת כל מה שלפניו, או את המספר השלילי האחרון ואת כל מה שאחריו. כך או כך, נשארים עם סיומת או עם תחילית של הרצף.
מעבר משמאל עם מכפלה מצטברת בודק כל תחילית, ומאפס אותה ל-1 אחרי 0. מעבר מימין בודק כל סיומת. עבור [-2, 3, -4, -1] המעבר משמאל רואה -2, -6, 24 ו--24, והמעבר מימין רואה -1, 4, 12 ו--24, ולכן התשובה היא 24. הטיעון דורש שהערך המוחלט של כל ערך שאינו אפס יהיה לפחות 1, וזה נכון עבור מספרים שלמים.
אלגוריתם
- הגדר את
bestל-nums[0]ואתproductל-1. - עבור משמאל לימין: הכפל את
productבכל איבר והשאר את הגדול מביןbestו-product. - בכל פעם ש-
productהופך ל-0, הגדר אותו שוב ל-1 כדי שהריצה הבאה תתחיל מחדש. - הגדר שוב את
productל-1 ובצע את אותה סריקה מימין לשמאל. - החזר את
best.
def maxProduct(nums):
best = nums[0]
# Left to right: the product of every prefix of each zero-free run
product = 1
for num in nums:
product *= num
best = max(best, product)
if product == 0:
product = 1 # a zero ends the run, the next one starts fresh
# Right to left: the product of every suffix of each zero-free run
product = 1
for num in reversed(nums):
product *= num
best = max(best, product)
if product == 0:
product = 1
return bestעקוב אחר המכפלה הגדולה ביותר והקטנה ביותר שמסתיימות כאן
האינטואיציה
כל תת־מערך שמסתיים באינדקס i הוא nums[i] לבדו, או nums[i] כפול תת־מערך שמסתיים ב־i-1. כש־nums[i] שלילי, המכפלה הגדולה ביותר מבין המכפלות האלה מתקבלת מהמכפלה הקטנה ביותר שמסתיימת ב־i-1. לכן שומרים את שניהם: high ו־low, המכפלות הגדולה והקטנה ביותר של תת־מערך שמסתיים באינדקס הנוכחי. high החדש הוא הגדול ביותר מבין num, high × num ו־low × num, ו־low החדש הוא הקטן ביותר. לקיחת num לבדו היא שמתחילה מחדש את הרצף אחרי אפס.
בדוגמה הראשונה, low הוא -30 כשמגיעים אל -2, ו־-30 × -2 = 60 הופך ל־high, התשובה.
אלגוריתם
- הגדר את
high, אתlowואתbestל־nums[0]. - עבור כל איבר מאוחר יותר
num, חשבa = high × numו־b = low × num. - הגדר את
highלערך הגדול ביותר ואתlowלערך הקטן ביותר מביןnum,aו־b. - הגדר את
bestלערך הגדול יותר מביןbestו־high. - החזר את
best.
def maxProduct(nums):
# high and low: the largest and smallest product of a subarray ending at the current index
high = low = best = nums[0]
for num in nums[1:]:
# Multiply both old values first: a negative num swaps their roles
a = high * num
b = low * num
high = max(num, a, b)
low = min(num, a, b)
best = max(best, high)
return best
מלכודות ומקרי קצה
- מעקב רק אחר המכפלה הגדולה ביותר. בדוגמה הראשונה, הערך המוחזר הוא 4 במקום 60, כי כך מאבדים את -30, שהופך ל־60 בעקבות הכפלה ב־-2.
- חישוב
lowהחדש מתוךhighשכבר עודכן. שמרו אתhigh × numואתlow × numלפני שתשנו אחד מהם. - אתחול
bestל־0 או ל־1. עבור[-3]יש להחזיר -3, כי תת־המערך אינו יכול להיות ריק. - הרצה של מעבר שמאלי בלבד בשיטת שני המעברים. עבור
[-2, 3, 4]הוא לעולם לא נתקל בערך גדול מ־-2, אבל הסיומת[3, 4]נותנת 12. - ב־JavaScript, ב־TypeScript וב־Lua, הכפלת 0 במספר שלילי נותנת
-0, שמודפס עם סימן מינוס. הוסיפו 0 לתוצאה לפני החזרתה.
שאלות נפוצות3
מהי סיבוכיות הזמן של תת־מערך המכפלה המרבית?
מעקב אחר המכפלה הגדולה ביותר והקטנה ביותר שמסתיימת בכל אינדקס דורש זמן O(n) ומקום O(1). שיטת הקידומות והסיומות בשני מעברים עולה אותו הדבר. הכפלת כל תת־מערך מכל נקודת התחלה דורשת זמן O(n²).
למה צריך את המכפלה המינימלית בתת־מערך בעל המכפלה המרבית?
מספר שלילי הופך את המכפלה השלילית ביותר שמסתיימת באינדקס הקודם לגדולה ביותר. אם שומרים רק את המכפלה הגדולה ביותר, המועמד הזה נעלם כשצריך אותו. ב־[3, -2, -4], המכפלה הקטנה ביותר לפני -4 היא -6, ו־-6 × -4 = 24 היא התשובה.
במה שונה תת-המערך בעל המכפלה המרבית מתת-המערך המרבי?
בסכומים, סכום מצטבר שלילי רק מזיק, ולכן מספיק ערך אחד לכל אינדקס. במכפלות, ערך שלילי מצטבר יכול להפוך לטוב ביותר אחרי מספר שלילי נוסף, ואפס מאפס את הכול. לכן גרסת המכפלה שומרת את המכפלה הגדולה ביותר ואת הקטנה ביותר בכל אינדקס.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def maxProduct(nums):
# כתבו את הקוד כאןבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [2, -5, 3, -2, 0, 4]
הפלט הצפוי
60