حداکثر مشکل زیرآرایه و الگوریتم کادان

مشکل حداکثر زیرآرایه و تاریخچه آن

در اواخر دهه 1970، اولف گرناندر، ریاضیدان سوئدی، درباره یک مسئله بحث می کرد: چگونه می توان یک آرایه 2 بعدی از داده های تصویر را کارآمدتر از نیروی بی رحمانه تجزیه و تحلیل کرد؟ کامپیوترها در آن زمان کند بودند و تصاویر نسبت به RAM بزرگ بودند. برای تشدید همه چیز، در بدترین حالت، نیروی بی رحمانه زمان O(n^6) را گرفت (پیچیدگی زمانی جنسی).

ابتدا، گرناندیر این سوال را ساده کرد: با توجه به یک آرایه یک بعدی از اعداد، چگونه می توانید زیرآرایه به هم پیوسته را با بیشترین مجموع به بهترین نحو پیدا کنید؟

نیروی بی رحم: رویکرد ساده لوحانه با پیچیدگی زمانی مکعبی

نیروی بی رحم، نیمی از زمان تجزیه و تحلیل یک آرایه یک بعدی نسبت به یک آرایه دو بعدی خواهد بود، بنابراین O(n^3) برای بررسی هر ترکیب ممکن (پیچیدگی زمانی مکعبی).

def max_subarray_brute_force(arr):
    max_sum = arr[0] # assumes arr has a length

    # iterate over all possible subarrays
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            current_sum = 0
            # sum the elements of the subarray arr[i:j+1]
            for k in range(i, j + 1):
                current_sum += arr[k]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

print(max_subarray_brute_force([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

بهینه سازی O(n²) Grenander: یک گام به جلو

گرناندر آن را به محلول O(n^2) ارتقا داد. من نتوانستم کد او را در تحقیقاتم پیدا کنم، اما حدس من این است که او به سادگی از درونی ترین حلقه خلاص شد که همه اعداد بین دو شاخص را جمع می کند. در عوض، می‌توانیم در حین تکرار روی زیرآرایه، یک مجموع در حال اجرا نگه داریم، بنابراین تعداد حلقه‌ها را از سه به دو کاهش می‌دهیم.

def max_subarray_optimized(arr):
    max_sum = arr[0]  # assumes arr has a length

    # iterate over all possible starting points of the subarray
    for i in range(len(arr)):
        current_sum = 0
        # sum the elements of the subarray starting from arr[i]
        for j in range(i, len(arr)):
            current_sum += arr[j]
            # update max_sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

    return max_sum

Shamos's Divide and Conquer: تقسیم مسئله برای O(n log n)

گرناندر مشکل را به دانشمند کامپیوتر مایکل شاموس نشان داد. شموس یک شب به این موضوع فکر کرد و روشی برای تقسیم و غلبه به وجود آورد که O(n log n) است.

این کاملا هوشمندانه است. ایده این است که آرایه را به دو نیمه تقسیم کنیم، سپس به صورت بازگشتی حداکثر مجموع زیرآرایه را برای هر نیمه و همچنین زیرآرایه ای که از نقطه میانی عبور می کند، پیدا کنیم.

def max_crossing_sum(arr, left, mid, right):
    # left of mid
    left_sum = float('-inf')
    current_sum = 0
    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        left_sum = max(left_sum, current_sum)

    # right of mid
    right_sum = float('inf')
    current_sum = 0
    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        right_sum = max(right_sum, current_sum)

    # sum of elements on the left and right of mid, which is the maximum sum that crosses the midpoint
    return left_sum + right_sum

def max_subarray_divide_and_conquer(arr, left, right):
    # base case: only one element
    if left == right:
        return arr[left]

    # find the midpoint
    mid = (left + right) // 2

    # recursively find the maximum subarray sum for the left and right halves
    left_sum = max_subarray_divide_and_conquer(arr, left, mid)
    right_sum = max_subarray_divide_and_conquer(arr, mid + 1, right)
    cross_sum = max_crossing_sum(arr, left, mid, right)

    # return the maximum of the three possible cases
    return max(left_sum, right_sum, cross_sum)

def max_subarray(arr):
    return max_subarray_divide_and_conquer(arr, 0, len(arr) - 1)


print(max_subarray([-2, -3, 4, -1, -2, 1, 5, -3]), "== 7")

این پیچیدگی زمانی را به زمان O(nlogn) کاهش می دهد زیرا ابتدا آرایه به دو نیمه (O(logn)) تقسیم می شود و سپس یافتن حداکثر زیرآرایه متقاطع به O(n) نیاز دارد.

الگوریتم Kadane: The Elegant O(n) Solution

Stastician Jay Kadane به کد نگاه کرد و بلافاصله متوجه شد که راه حل Shamos در استفاده از مهار مجاورت به عنوان بخشی از راه حل شکست خورده است.

این چیزی است که او متوجه شد

-اگر یک آرایه فقط اعداد منفی داشته باشد، با فرض اینکه اجازه نداریم زیرآرایه های خالی را مجاز نکنیم، پاسخ همیشه بزرگترین عدد در آرایه خواهد بود.

-اگر یک آرایه فقط دارای اعداد مثبت باشد، پاسخ همیشه جمع کردن کل آرایه خواهد بود.

-اگر آرایه ای از اعداد مثبت و منفی دارید، می توانید گام به گام آرایه را طی کنید. اگر در هر نقطه ای عددی که به آن نگاه می کنید بزرگتر از مجموع تمام اعداد قبل از آن باشد، راه حل نمی تواند شامل هیچ یک از اعداد قبلی باشد. بنابراین، شما یک مجموع جدید را از عدد فعلی شروع می‌کنید، در حالی که حداکثر مبلغی را که تاکنون با آن مواجه شده‌اید را پیگیری می‌کنید.

maxSubArray(nums):
    # avoiding type errors or index out of bounds errors
    if nums is None or len(nums) == 0:
        return 0


    max_sum = nums[0]  # max sum can't be smaller than any given element
    curr_sum = 0

    # Kadane's algorithm
    for num in nums:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(curr_sum, max_sum)
    return max_sum

چیزی که من در مورد این الگوریتم دوست دارم این است که می توان آن را برای بسیاری از مشکلات دیگر اعمال کرد. سعی کنید آن را برای حل این مشکلات LeetCode تطبیق دهید:

یک ها و صفرها
ماکزیمم جمع دایره ای فرعی
حداقل اندازه سابرای جمع
حداکثر مجموع زیرآرایه صعودی
حداکثر محصول فرعی
مجموع زیرآبی پیوسته
حداکثر مجموع متناوب فرعی (حق بیمه)
حداکثر مجموع مستطیل بدون بزرگتر از K