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.
سؤال إضافي
هل يمكنك أيضًا إرجاع موضع بداية أفضل نافذة، واختيار النافذة الواقعة إلى أقصى اليسار عند التعادل بين عدة نوافذ؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب مجموع نافذتين متجاورتين، لنقل النافذة التي تبدأ عند الفهرس 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على أصغر قيمة ممكنة. - لكل قيمة لـ start من
0إلىn-k، اضبطtotal = 0. - أضف القيم من
nums[start]حتىnums[start+k-1]إلىtotal. - إذا تجاوزت قيمة
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، تكون تلك هي النافذة الوحيدة، وقد يؤدي خطأ بمقدار واحد إلى عدم فحص أي نافذة وإرجاع القيمة الابتدائية لـbest. - إجراء المقارنة بعد انتهاء الحلقة فقط. قد تكون أفضل نافذة هي الأولى، لذا قارن مجموع النافذة الأولى أيضًا، أو هيّئ
bestباستخدامه. - نسيان أن العد في R وLua يبدأ من 1. النافذة الأولى هي
nums[1..k]، والعنصر الذي يخرج عند دخولnums[i]يظلnums[i-k].
أسئلة شائعة3
ما هي النافذة المنزلقة ذات الحجم الثابت؟
إنه نطاق يتكوّن من 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، لذا فإن كل مرشّح عبارة عن نافذة، ويغطيها مجموع منزلق. في مسألة المصفوفة الفرعية العظمى، يكون الطول غير محدد، وتحتاج إلى خوارزمية كادين، التي تقرر عند كل عنصر ما إذا كانت ستمدّد المقطع الحالي أم تبدأ مقطعًا جديدًا. لا تملك النافذة الثابتة هذا الخيار.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxSumSubarray(nums, k):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [4, -1, 3, 7, -2, 5, 1] k = 3
الإخراج المتوقع
10