حلولي في كودرهب

المصفوفة المتصلة

سهل5 نقاطPython

الوصف

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

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

المهمة:

لديك مصفوفة تحتوي على أعداد صحيحة (موجبة وسالبة). مهمتك هي اختيار جزء متصل من هذه المصفوفة بحيث يكون مجموع عناصره هو الأكبر بين جميع الخيارات الممكنة.المثال :

  • المدخل: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

  • الإخراج: 6

  • الشرح: الجزء المتصل من المصفوفة الذي يحقق أكبر مجموع هو [4, -1, 2, 1]. المجموع: 4 + (-1) + 2 + 1 = 6.

أمثلة

المدخلاتالمخرجات المتوقعة
nums = [-2,1,-3,4,-1,2,1,-5,4]6
nums = [1]1
nums = [5,4,-1,7,8]23
nums = [-1,-2,-3,-4]-1

الحل

from typing import List
def maxSubArray(nums: List[int]) -> int:
    max_sum = nums[0]
    cur = nums[0]
    for num in nums[1:]:
        cur = max(num, cur + num)
        max_sum = max(max_sum, cur)
    return max_sum

في هذه الصفحة