Maximum Sum Subarray of Size K

Q: ما هي النافذة المنزلقة ذات الحجم الثابت؟

إنه نطاق يتكوّن من k عناصر متجاورة بالضبط، ويتحرك خطوة واحدة في كل مرة عبر مصفوفة. بدلًا من إعادة حساب النطاق من البداية عند كل موضع، تحدّث قيمةً تراكمية: أضف العنصر الذي يدخل من اليمين وأزل العنصر الذي يخرج من اليسار. يحوّل ذلك العمل من O(n·k) إلى O(n) .

Q: ما هو التعقيد الزمني لإيجاد المصفوفة الفرعية ذات الحجم k ذات أكبر مجموع؟

باستخدام نافذة منزلقة، يكون التعقيد الزمني O(n) والمساحة الإضافية O(1) : مرور واحد لجمع عناصر النافذة الأولى، ثم عملية جمع وعملية طرح في كل خطوة. أما جمع عناصر كل نافذة على حدة فيتطلب (n-k+1) × k عملية جمع، أي O(n·k) ، ونحو 2.5 × 10^7 عندما تكون n = 10^4 و k = 5000 .

Q: ما الفرق بين هذه المسألة ومسألة المصفوفة الفرعية ذات المجموع الأقصى؟

هنا يكون الطول ثابتًا عند k ، لذا فإن كل مرشّح عبارة عن نافذة، ويغطيها مجموع منزلق. في مسألة المصفوفة الفرعية العظمى، يكون الطول غير محدد، وتحتاج إلى خوارزمية كادين، التي تقرر عند كل عنصر ما إذا كانت ستمدّد المقطع الحالي أم تبدأ مقطعًا جديدًا. لا تملك النافذة الثابتة هذا الخيار.

Q: هل يمكن للمجاميع التراكمية حلّها أيضًا؟

نعم. أنشئ prefix[i] بوصفه مجموع أول i عناصر، ويكون مجموع النافذة التي تبدأ عند s هو prefix[s+k] - prefix[s] . وهذا أيضًا يستغرق زمنًا قدره O(n) ، لكنه يخزّن n+1 من المجاميع. تحصل النافذة المنزلقة على المجاميع نفسها باستخدام متغيرين.

سهلالنافذة المنزلقة

+10

لديك مصفوفة من الأعداد الصحيحة nums وطول نافذة k. انظر إلى كل مجموعة متتالية تتكوّن من k عناصر متجاورة تمامًا، وأعِد أكبر مجموع بينها. قد تكون القيم سالبة، لذا قد تكون الإجابة سالبة أيضًا.

الدالة

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: مصفوفة الأعداد الصحيحة
kinteger: عدد العناصر المجاورة التي تحتويها كل نافذة
تُرجعinteger: أكبر مجموع لأي k عناصر متتالية

القيود

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

أمثلة

المدخلات: 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 من 3

الحل

هناك 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].

أسئلة شائعة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، لذا فإن كل مرشّح عبارة عن نافذة، ويغطيها مجموع منزلق. في مسألة المصفوفة الفرعية العظمى، يكون الطول غير محدد، وتحتاج إلى خوارزمية كادين، التي تقرر عند كل عنصر ما إذا كانت ستمدّد المقطع الحالي أم تبدأ مقطعًا جديدًا. لا تملك النافذة الثابتة هذا الخيار.

هل يمكن للمجاميع التراكمية حلّها أيضًا؟

نعم. أنشئ 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

المتوقع