ما هي خوارزمية كادان ؟

تلك خوارزمية لحل مشكلة أقصى مجموع جزئي  أو أكبر مجموع فرعي متجاور Maximum Subarray Problem، وذلك لإيجاد المجموع الأعظمي لتسلسل فرعي متجاور ضمن مصفوفة أحادية البعد تحتوي على أرقام قد تكون موجبة أو سالبة.

تحتفظ الخوارزمية بمتغيرين max_so_far يمثل أقصى مجموع تم العثور عليه حتى الآن، و max_ending_here يمثل أقصى مجموع ينتهي عند العنصر الحالي.

ثم تمر عبر عناصر المصفوفة:

• لكل عنصر، تضيف قيمته إلى max_ending_here.
• وإن أصبح max_ending_here سالبًا، تعيد تعيينه إلى الصفر لأن البدء من جديد أفضل من الاستمرار بمجموع سالب.
• ثم تحديث max_so_far في حال max_ending_here أكبر منه.

بعد الإنتهاء تعيد max_so_far كنتيجة.

وذلك مثال من خلال جافاسكريبت:

let array =  [-2, 1, -3, 4, -1, 2, 1, -5, 4]

function maxSubArray(array) {
    let current_sum = array[0]
    let max_sum = array[0]

    for (let i = 1; i < array.length; i++) {
        current_sum = Math.max(array[i], current_sum + array[i])

        if (current_sum > max_sum) {
            max_sum = current_sum
        }
    }

    return max_sum
}

console.log(maxSubArray(array))		

تمام جدا 

الف شكراا جدا لحضرتك

جزاك الله كل خير

Kadane's Algorithm هي خوارزمية خطية تستخدم لإيجاد أكبر مجموع لمصفوفة فرعية في مصفوفة معينة تعرف المصفوفة الفرعية بأنها مجموعة متصلة من العناصر داخل المصفوفة وتتعامل الخوارزمية بفاعلية مع الأرقام الموجبة والسالبة، مما يجعلها أداة متعددة الاستخدامات لحل العديد من المشكلات المتعلقة بالمصفوفات الفرعية.

تعتمد الخوارزمية على منهج البرمجة الديناميكية من خلال حساب أكبر مجموع متصل ينتهي عند كل عنصر في المصفوفة والفكرة الأساسية هي مقارنة العنصر الحالي بأكبر مجموع متصل سابق، وتحديث القيم بناء على ذلك ولتنفيذها نقوم بالتالي أولا نقوم بتهيئة متغيرين:

• max_so_far: أكبر مجموع متصل تم العثور عليه حتى الآن.
• max_ending_here: المجموع المتصل الحالي.

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

وعند الانتهاء من المرور على المصفوفة، سيحتوي max_so_far على أكبر مجموع متصل على هذا النحو:

public class KadaneAlgorithm {
    public static int maxSubarraySum(int[] arr) {
        int max_so_far = Integer.MIN_VALUE;
        int max_ending_here = 0;

        for (int i = 0; i < arr.length; i++) {
            max_ending_here += arr[i];
            if (max_ending_here < 0) {
                max_ending_here = 0;
            }
            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }
        }

        return max_so_far;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = maxSubarraySum(arr);
        System.out.println("أكبر مجموع متصل هو: " + maxSum);
    }
}

ثم الإخراج سيكون:

أكبر مجموع متصل هو: 6

وهو ناتج جمع [4, -1, 2, 1].

أما بالنسبة للتعقيد الزمني لهذه الخوارزنية فهو O(n) حيث n هو عدد عناصر المصفوفة.