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. يقسم الصفر المصفوفة إلى قسمين، والعدد 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 الذي يحوّله -2 إلى 60.
- حساب
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