خوارزمية كادان هي أسلوب برمجة ديناميكي يستخدم لحل مشكلة الحد الأقصى للمصفوفة الفرعية، والتي تتضمن إيجاد المصفوفة الفرعية المتجاورة مع الحد الأقصى للمجموع في مجموعة من الأرقام. تم اقتراح الخوارزمية بواسطة جاي كادان في عام 1984 ولها تعقيد زمني قدره O(n).
تاريخ خوارزمية كادان:
تم تسمية خوارزمية كادان على اسم مخترعها، جاي كادان، أستاذ علوم الكمبيوتر في جامعة كارنيجي ميلون. وصف الخوارزمية لأول مرة في ورقة بحثية بعنوان 'مشكلة المصفوفة الفرعية القصوى' نُشرت في مجلة جمعية آلات الحوسبة (ACM) في عام 1984.
تمت دراسة مشكلة العثور على الحد الأقصى للصفيف الفرعي من قبل علماء الكمبيوتر منذ السبعينيات. إنها مشكلة معروفة في مجال تصميم الخوارزميات وتحليلها ولها تطبيقات في مجموعة واسعة من المجالات، بما في ذلك معالجة الإشارات والتمويل والمعلوماتية الحيوية.
قبل خوارزمية كادان، تم اقتراح خوارزميات أخرى لحل مشكلة المصفوفة الفرعية القصوى، مثل نهج القوة الغاشمة الذي يتحقق من جميع المصفوفات الفرعية الممكنة وخوارزمية فرق تسد. ومع ذلك، فإن هذه الخوارزميات لديها تعقيدات زمنية أعلى وأقل كفاءة من خوارزمية كادان.
تُستخدم خوارزمية كادان على نطاق واسع في علوم الكمبيوتر وأصبحت مثالًا كلاسيكيًا للبرمجة الديناميكية. إن بساطته وكفاءته وأناقته جعلته حلاً شائعًا لمشكلة المصفوفة الفرعية القصوى وأداة قيمة في تصميم الخوارزميات وتحليلها.
عمل خوارزمية كادين:
تعمل الخوارزمية من خلال التكرار على المصفوفة وتتبع الحد الأقصى لمجموع المصفوفة الفرعية التي تنتهي عند كل موضع. في كل موضع i، لدينا خياران: إما إضافة العنصر في الموضع i إلى الحد الأقصى للمصفوفة الفرعية الحالية أو بدء مصفوفة فرعية جديدة في الموضع i. الحد الأقصى لهذين الخيارين هو الحد الأقصى للمصفوفة الفرعية التي تنتهي عند الموضع i.
نحتفظ بمتغيرين، max_so_far وmax_ending_here، لتتبع الحد الأقصى للمبلغ الذي تم رؤيته حتى الآن والحد الأقصى للمبلغ المنتهي عند الموضع الحالي، على التوالي. تبدأ الخوارزمية بتعيين كلا المتغيرين على العنصر الأول في المصفوفة. ثم نقوم بالتكرار على المصفوفة من العنصر الثاني إلى النهاية.
في كل موضع i، نقوم بتحديث max_ending_here عن طريق أخذ الحد الأقصى للعنصر الحالي والعنصر الحالي المضاف إلى الحد الأقصى للمصفوفة الفرعية السابقة. نقوم بعد ذلك بتحديث max_so_far ليكون الحد الأقصى لـ max_so_far وmax_ending_here.
الممثلة الهندية راني موخرجي
تقوم الخوارزمية بإرجاع max_so_far، وهو الحد الأقصى لمجموع أي صفيف فرعي في المصفوفة.
فيما يلي عملية خطوة بخطوة لخوارزمية Kadane:
1. تهيئة متغيرين، max_so_far و max_ending_here ، إلى العنصر الأول من المصفوفة.
max_so_far = آر[0]
max_ending_here = arr[0]
2. قم بالتكرار على المصفوفة من العنصر الثاني إلى النهاية:
لأني من 1 إلى n-1 أفعل:
3. احسب الحد الأقصى للمبلغ المنتهي عند الموضع الحالي:
ما هو السبات
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. قم بتحديث max_so_far ليكون الحد الأقصى لـ max_so_far وmax_ending_here:
max_so_far = الحد الأقصى (max_so_far، max_ending_here)
5. قم بإرجاع max_so_far كأقصى مجموع لأي مصفوفة فرعية في المصفوفة.
التعقيد الزمني لخوارزمية كادان هو O(n)، حيث n هو طول مصفوفة الإدخال. وهذا يجعله حلاً فعالاً للغاية لمشكلة المصفوفة الفرعية القصوى.
مثال:
دعونا نرى مثالاً لكيفية عمل خوارزمية كادان:
لنفترض أن لدينا المصفوفة التالية من الأعداد الصحيحة:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
نريد إيجاد الحد الأقصى لمجموع المصفوفة الفرعية لهذه المصفوفة. يمكننا تطبيق خوارزمية كادان لحل هذه المشكلة.
نبدأ بتهيئة متغيرين:
max_so_far = INT_MIN; max_ending_here = 0;
ثم نكرر خلال المصفوفة بدءًا من العنصر الثاني:
اصطلاحات تسمية جافا
for i in range(1, len(arr)):
قم بتحديث المجموع الحالي عن طريق إضافة العنصر الحالي إلى المجموع السابق:
max_ending_here = max(arr[i], max_ending_here + arr[i])
قم بتحديث الحد الأقصى للمبلغ الذي تمت مشاهدته حتى الآن:
max_so_far = max(max_so_far, max_ending_here)
في كل تكرار، نقوم بتحديث المجموع الحالي إما عن طريق إضافة العنصر الحالي إلى المجموع السابق أو بدء مصفوفة فرعية جديدة في العنصر الحالي. نقوم بعد ذلك بتحديث الحد الأقصى للمبلغ الذي تم رؤيته حتى الآن من خلال مقارنته بالمبلغ الحالي.
بعد التكرار عبر المصفوفة بأكملها، ستكون قيمة max_so_far هي الحد الأقصى لمجموع المصفوفة الفرعية للمصفوفة المحددة.
في هذا المثال، الحد الأقصى لمجموع المصفوفة الفرعية هو 6، وهو ما يتوافق مع المصفوفة الفرعية [4, -1, 2, 1].
تنفيذ التعليمات البرمجية في جافا:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print('Enter the size of the array : '); int n=sc.nextInt(); int[] arr=new int[n]; System.out.println('Enter the elements of the array : '); for(int i=0;i<n;i++){ arr[i]="sc.nextInt();" } int max_so_far="Integer.MIN_VALUE,max_ending_here=0;" for(int i="0;i<n;i++)" { max_ending_here+="arr[i];" if(max_so_far<max_ending_here){ if(max_ending_here<0){ max_ending_here="0;" system.out.print('the maximum contiguous sum in the array is : '+max_so_far); < pre> <p> <strong>Output</strong> </p> <pre> Enter the size of the array : 9 Enter the elements of the array : -2 1 -3 4 -1 2 1 -5 4 The Maximum contiguous sum in the array is : 6 </pre> <h3>Code Implementation in C++:</h3> <pre> #include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << 'maximum contiguous sum in the array is : '<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;></pre></n;i++){> تنفيذ التعليمات البرمجية في C++:
#include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << \'maximum contiguous sum in the array is : \'<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;> مزايا وعيوب خوارزمية كادان:
مزايا خوارزمية كادان:
عيوب خوارزمية كادان:
تطبيقات خوارزمية كادان:
وهناك بعض تطبيقاته مثل ما يلي:
لذلك، يمكننا القول أن مزايا خوارزمية كادان تجعلها حلاً رائعًا لحل مشكلة الحد الأقصى للمصفوفة الفرعية، خاصة لمجموعات البيانات الكبيرة. ومع ذلك، يجب مراعاة حدوده عند استخدامه لتطبيقات محددة.