سوال 53

عنوان سوال : Maximum Subarray

• متوسط
• تقسیم و غلبه
• برنامه نویسی پویا
• آرایه

---

یک آرایهٔ عدد صحیح nums داده شده است.
هدف این است که بزرگ‌ترین مجموع یک زیرآرایهٔ پیوسته را پیدا کرده و مقدار آن را برگردانید.

---

مثال

ورودی: nums = [-2,1,-3,4,-1,2,1,-5,4]
خروجی: 6
توضیح: زیرآرایهٔ [4,-1,2,1] بیشترین مجموع را دارد که برابر با 6 است.

---

مثال

ورودی: nums = [1]
خروجی: 1
توضیح: زیرآرایهٔ [1] بیشترین مجموع را دارد.

---

مثال

ورودی: nums = [5,4,-1,7,8]
خروجی: 23
توضیح: زیرآرایهٔ [5,4,-1,7,8] بیشترین مجموع را دارد.

---

محدودیت‌ها

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

راه حل

public int MaxSubArray(int[] nums)
{
    var maxSubArrayValue = nums[0];
    var currentSum = 0;

    foreach (var item in nums)
    {
        if (currentSum < 0)
        {
            currentSum = 0;
        }

        currentSum += item;
        maxSubArrayValue = Math.Max(maxSubArrayValue, currentSum);
    }

    return maxSubArrayValue;
}