خوارزمية كادينس: أكبر مجموعة فرعية متجاورة

ما هو أكبر مجموع للمصفوفة الفرعية المتجاورة؟

المصفوفة الفرعية هي جزء مستمر من المصفوفة. يمكن أن يكون عنصرًا واحدًا من المصفوفة أو جزءًا من المصفوفة. أكبر صفيف فرعي متجاور يعني صفيفًا فرعيًا له الحد الأقصى لقيمة المجموع.

على سبيل المثال، لنأخذ المصفوفة {-10، 5، 1، 6، -9، 2، -7، 3، -5}. يمكن أن تكون مصفوفاتها الفرعية {-10، 5، 1، 6}، أو {5، 1، 6}، أو {2، -7، 3، -5}، وهكذا. مع ذلك، لا يمكن أن تكون {5، 1، 6، 3} مصفوفة فرعية لأن عناصرها ليست متسلسلة.

إذا لاحظت، من بين جميع المصفوفات الفرعية، فإن المصفوفة الفرعية المميزة {5، 1، 6} لها أعلى قيمة مجموع:

مجموع المصفوفة الفرعية {5، 1، 6} هو 12، وهو أكبر مجموع ممكن بين جميع المصفوفات الفرعية الممكنة للمصفوفة المذكورة أعلاه. لذا، بالنسبة لهذه المصفوفة، فإن أكبر مجموع للمصفوفة الفرعية المتجاورة هو {5، 1، 6}.

طريقة بسيطة لحل مصفوفة فرعية متجاورة ذات أكبر مجموع

الطريقة البسيطة لحل هذه المشكلة هي استخدام حلقتين للعثور على جميع المصفوفات الفرعية، وحساب المجموع، ثم العثور على القيمة القصوى لها.

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

فيما يلي الخطوات البسيطة للقيام بذلك.

الخطوة 1) تهيئة المجموع الأقصى بأقل قيمة عددية صحيحة، ثم حدد بدأ و النهاية إلى الصفر.

الخطوة 2) اسمحوا i و j تكون مؤشرات المصفوفة حيث j أكبر من أو يساوي i; i يُشير إلى بداية المصفوفة الفرعية و j نهايتها.

الخطوة 3) المجموع الحالي يحتوي على المجموع التراكمي. بعد كل تحديث، تحقق مما إذا كان المجموع الحالي أكبر من المجموع الأقصى.

الخطوة 4) If المجموع الحالي إذا كان أكبر، استبدل المجموع الأقصى معها.

الخطوة 5) متى j عند الوصول إلى نهاية المصفوفة، قم بزيادة العداد i وإعادة تعيين المجموع الحالي ل0.

الخطوة 6) كرر حتى i يصل إلى نهاية المصفوفة. المجموع الأقصى ثم يحتوي على أكبر مجموع للمصفوفة الفرعية.

كنية Code لنهج بسيط

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ تنفيذ النهج البسيط

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

الإخراج:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python تنفيذ النهج البسيط

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

الإخراج:

largest sum is 12
largest sum contiguous subarray: 5      1       6

خوارزمية كادان لإيجاد أكبر مجموع للمصفوفة الفرعية المتجاورة

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

نحتاج فقط إلى متغيرين لإيجاد أكبر مجموع لمصفوفة فرعية متجاورة. إليك مخطط التدفق:

فيما يلي خطوات خوارزمية كادان:

الخطوة 1) أنشئ متغيرين، المجموع الحالي و المجموع الأقصى.

المجموع الحالي يحتفظ بأقصى مجموع ينتهي عند فهرس محدد في المصفوفة، بينما المجموع الأقصى يخزن أكبر قيمة إجمالية تم رصدها حتى الآن.

الخطوة 2) أضف كل عنصر من عناصر المصفوفة إلى المجموع الحاليثم تحقق من الشرطين التاليين:

• If المجموع الحالي إذا كان أقل من العنصر الحالي، المجموع الحالي يصبح العنصر الحالي.
• If المجموع الأقصى أقل من المجموع الحالي، ثم المجموع الأقصى يصبح المجموع الحالي.

الخطوة 3) بعد تكرار الخطوة السابقة للمصفوفة بأكملها، المجموع الأقصى يحتوي على أكبر مجموع للمصفوفة الفرعية المتجاورة.

مثال على خوارزمية كادان

نوضح خوارزمية كادان على مصفوفة صغيرة ونستعرض كل خطوة من خطوات إيجاد أكبر مجموع للمصفوفة الفرعية المتجاورة.

لنفترض أن المصفوفة المعطاة تشبه ما يلي:

فيما يلي خطوات خوارزمية كادان:

الخطوة 1) أنشئ متغيرين، المجموع الحالي و المجموع الأقصىقم بتعيين INT_MIN إلى المجموع الأقصى ومن صفر إلى المجموع الحاليهنا، يمثل INT_MIN أصغر قيمة عددية صحيحة.

الخطوة 2) عند الفهرس 0، تكون القيمة 4. لذا، المجموع الحالي = 0 + 4 = 4. بما أن المجموع الحالي أكبر من المجموع الأقصى, المجموع الأقصى يصبح 4.

الخطوة 3) عند الفهرس 1، تكون القيمة -2. لذا، المجموع الحالي = 4 + (-2) = 2.

هذا الوقت المجموع الحالي أقل من المجموع الأقصىونتيجة لذلك، فإن قيمة المجموع الأقصى لم يتم تحديثه.

الخطوة 4) القيمة التالية هي 1. بإضافتها إلى المجموع الحالي يعطي 3. بما أن المجموع الأقصى (4) لا يزال أكبر من المجموع الحالي, المجموع الأقصى لم يتم تحديثه.

الخطوة 5) عند الفهرس 3، تكون القيمة 3. زيادة المجموع الحالي بضربها في 3 تعطي المجموع الحالي = 6.

في هذه الحالة، المجموع الأقصى أصغر من المجموع الحالي، وبالتالي المجموع الأقصى يتم تحديثها بقيمة المجموع الحالي.

الخطوة 6) بالنسبة للعنصر الأخير في المصفوفة، لدينا -1. بإضافته إلى المجموع الحالي يعطي 5، وهو أصغر من المجموع الأقصى. وبالتالي، المجموع الأقصى يتبقى 6.

عندما وصلنا إلى نهاية المصفوفة، تنتهي الخوارزمية هنا. الآن، المجموع الأقصى تحتوي على أكبر مجموع، وهو 6. المصفوفة الفرعية هي {4، -2، 1، 3}.

كنية Code لخوارزمية كادان

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ تنفيذ خوارزمية كادان

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

الإخراج:

largest sum is 12

Python تنفيذ خوارزمية كادان

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

الإخراج:

largest sum is 12

تحليل التعقيد لمجموع أكبر مجموعة فرعية متجاورة

تعتمد الطريقة البسيطة على استخدام حلقتين لحساب كل مجموع ممكن للمصفوفة الفرعية وتحديد أكبر مجموع. وهي طريقة تعتمد على البحث الشامل؛ حيث تستمر كل حلقة حتى نهاية المصفوفة. مجموعة، إعطاء O(N²) مرة.

تستخدم خوارزمية كادان حلقة واحدة فقط، مما يوفر زمنًا قدره O(N) ومساحة إضافية قدرها O(1). على مصفوفة مكونة من 100 عنصر، تُجري الطريقة البسيطة 100 × 100 = 10,000 عملية، بينما تُجري خوارزمية كادان 100 عملية فقط - وهو تسارع هائل للمدخلات الكبيرة.

الأسئلة الشائعة