٢٩ مايو ٢٠٢٠

المصفوفات

تسمح لك الكائنات بتخزين مجموعه من المفاتيح ذات قيم .الي الان هذا جيد .

ولكن في كثير من الأحيان نجد أننا بحاجة إلى مجموعة مرتبة, حيث لدينا عنصر الأول والثاني والثالث وما إلى ذلك. علي سبيل المثال, نحن نحتاج الي تخزين مجموعه من الشياء: مسخدمين, بضائع, عناصر HTML الخ.

ليس من المناسب ان نستخدم كائن هنا, لانه لايمتلك اي وسائل او طرق لترتيب العناصر. لايمكنا ادراج خاصيه جديده “بين” الموجوده بالفعل. الكائنات ليست معده لهذا الاستخدام فقط.

يوجد هيكل بيانات خاص يسمي Array, لتخزين المجموعات المرتبه.

الاعلان

هناك طريقتين لإنشاء مصفوفه فارغه:

let arr = new Array();
let arr = [];

في جميع الأوقات تقريبًا ، يتم استخدام بناء الجملة الثاني. يمكننا توفير العناصر الأولية في الأقواس:

let fruits = ["البرقوق", "البرتقال", "التفاح"];

يتم ترقيم عناصر المصفوفه ، بدءًا من صفر. يمكننا الحصول على عنصر من خلال الترقيم بين قوسين معقوفين:

let fruits = ["البرقوق", "البرتقال", "التفاح"];

alert( fruits[0] ); // التفاح
alert( fruits[1] ); // البرتقال
alert( fruits[2] ); // البرقوق

يمكننا استبدال عنصر:

fruits[2] = 'الكمثري'; // الآن ["التفاح", "البرتقال", "الكمثري"]

…او اضف واحد جديد الي المصفوفه :

fruits[3] = 'الليمون'; // الآن ["الليمون", "الكمثري", "البرتقال", "التفاح"]

العدد الإجمالي للعناصر في المصفوفه هو length:

let fruits = ["البرقوق", "البرتقال", "التفاح"];

alert( fruits.length ); // 3

يمكن ان نستخدم alert حتي نعرض المصفوفه كامله.

let fruits = ["البرقوق", "البرتقال", "التفاح"];

alert( fruits ); // البرقوق,البرتقال,التفاح

يمكن للمصفوفه ان تخزن عناصر من جميع الانواع.

على سبيل المثال:

// مزيج من القيم
let arr = [ 'التفاح', { name: 'جوهان' }, true, function() { alert('اهلا'); } ];

// احصل على الكائن في الفهرس 1 ثم إظهار اسمه
alert( arr[1].name ); // جوهان

// احصل على الكائن في الفهرس 3 ثم إظهار اسمه
arr[3](); // اهلا
الفاصلة اللاحقة

المصفوفه ، تمامًا مثل الكائن ، قد تنتهي بفاصلة:

let fruits = [
  "التفاح",
  "البرتقال",
  "البرقوق",
];

يسهّل نمط “الفاصلة اللاحقة” إدراج / إزالة العناصر ، لأن جميع الخطوط متشابهة.````

وسائل pop/push, shift/unshift

الطابور هو أحد الاستخدامات الأكثر شيوعًا للمصفوفة. في علوم الحاسب, هذا يعني مجموعة مرتبة من العناصر التي تدعم عمليتين:

  • pushإلحاق عنصر إلي النهاية.
  • shift احصل على عنصر من البداية ، بدفع قائمة الانتظار ، بحيث يصبح العنصر الثاني هو الأول.

تدعم المصفوفات كلا من العمليتين. في الممارسة العملية نحن بحاجة إليها في كثير من الأحيان. على سبيل المثال ،مجموعه الرسائل التي يجب عرضها على الشاشة. هناك حالة استخدام أخرى للمصفوفات – هيكل البيانات يسمي stack.

يدعم عمليتين:

  • push يضيف عنصرًا إلى النهاية.
  • pop يأخذ عنصر من النهاية.

لذلك يتم إضافة عناصر جديدة أو أخذها دائمًا من “النهايه”.

الكومه(stack) عادة ما يتم توضيحها كحزمة من البطاقات: تتم إضافة بطاقات جديدة إلى الأعلى أو مأخوذة من الأعلى:

بالنسبه للكومه(stacks), يتم استلام أحدث عنصر مدفوع أولاً ، وهذا ما يسمى بمبدأ LIFO (Last-In-First-Out). بالنسبة لقوائم الانتظار ، لدينا FIFO (First-In-First-Out).

يمكن أن تعمل المصفوفات في JavaScript كقائمة انتظار وكمجموعة(stack). تتيح لك إضافة / إزالة عناصر من / إلى البداية أو النهاية.

في علم الحاسوب يسمى هيكل البيانات الذي يسمح بذلك deque.

الأساليب التي تعمل مع نهاية المصفوفه:

pop :تعمل علي استخراج العنصر الأخير من المصفوفة وتعيده :

```js run
 ;["الكمثري", "البرتقال", "التفاح"] = let fruits

 ;alert( fruits.pop() ) // قم بإزاله "الكمثري" وقم بالعرض في تنبيه

 ;alert( fruits ) // البرتقال, التفاح
```
push

ألحق العنصر بنهاية المصفوفة:

let fruits = ["البرتقال", "التفاح"];

fruits.push("الكمثري");

alert( fruits ); // الكمثري, البرتقال, التفاح

تنفيذ هذا الكود الاتي (...)fruits.push يساوي تماما fruits[fruits.length] = ....

الأساليب التي تعمل مع بدايه المصفوفه:

shift

تعمل علي استخراج العنصر الاول من المصفوفة وتعيده:

let fruits = ["الكمثري", "البرتقال", "التفاح"];

alert( fruits.shift() ); // قم بإزاله التفاح وقم بالعرض في تنبيه

alert( fruits ); // الكمثري, البرتقال
unshift

إضافه العنصر في بدايه المصفوفه:

let fruits = ["الكمثري", "البرتقال"];

fruits.unshift('التفاح');

alert( fruits ); // الكمثري, البرتقال, التفاح

الوسائل push و unshift يمكنهم إضافة عناصر متعددة في وقت واحد:

let fruits = ["التفاح"];

fruits.push("خوخ", "البرتقال");
fruits.unshift("الليمون", "أناناس");

// ["الخوخ", "البرتقال", "التفاح", "الليمون", "أناناس"]
alert( fruits );

البنيه الداخليه للمصفوفه

المصفوفه هي نوع خاص من الكائن. الأقواس المربعة تستخدم للتحكم في الخاصيه arr[0] في الواقع تأتي من بناء الكائن. هذا في الاساس نفس obj[key], عندما تكون arr كائن, بينما الارقام تستخدم كمفاتيح.

إنها تمد الكائنات التي توفر وسائل خاصة للعمل مع مجموعات البيانات المطلوبة وكذلك خاصية `length '. ولكن في جوهرها لا يزال كائن. تذكر,لا يوجد سوى 7 أنواع أساسية في جافا سكريبت. المصفوفه عباره عن كائن لذالك هي تتصرف مثله.

على سبيل المثال, يتم نسخه حسب المرجع:

let fruits = ["الموز"]

let arr = fruits; // نسخ عن طريق المرجع (متغيران يشيران إلى نفس المصفوفة)
alert( arr === fruits ); // صحيح

arr.push("الكمثري"); // تعديل المصفوفه حسب المرجع

alert( fruits ); // الموز ، الكمثرى - 2 من العناصر الآن

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

لكن جميعها تنكسر إذا توقفنا عن العمل مع مصفوفة كما هو الحال مع “مجموعة مرتبة” وبدأنا في العمل معها كما لو كانت كائنًا عاديًا.

على سبيل المثال ، من الناحية الفنية يمكننا القيام بذلك:

let fruits = []; // إنشاء مصفوفه

fruits[99999] = 5; // قم بتعيين الخاصيه مع الفهرس أكبر بكثير من طوله

fruits.age = 25; // أنشئ الخاصيه باسم افتراضي

هذا ممكن ، لأن المصفوفات هي كائن في أساسها. يمكننا إضافة أي خصائص لهم.

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

طرق إساءة استخدام مصفوفة:

  • أضف خاصية غير رقمية مثل arr.test = 5.
  • اصنع فراغ, مثل: إضافه arr[0] وثم arr[1000] (ولا شيء بينهما).
  • املأ المصفوفة بالترتيب العكسي, مثل arr[1000], arr[999] وما إلي ذالك.

يرجى التفكير في المصفوفات كبنى خاصة للعمل مع * البيانات المطلوبة *. أنها توفر أساليب خاصة لذلك.يتم ضبط المصفوفات بعنايةداخل محركات JavaScript للعمل مع البيانات المرتبة المتجاورة ، يرجى استخدامها بهذه الطريقة. وإذا كنت بحاجة إلى مفاتيح عشوائية ،هناك احتمالات عالية بأنك تحتاج بالفعل إلى كائن عادي {}.

الأداء

الوسائل push/pop يتم تنفيذها أسرع, بينما shift/unshift تكون أبطئ.

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

fruits.shift(); // قم بأخذ عنصر من البدايه

لا يكفي أخذ العنصر وإزالته بالرقم 0.يجب إعادة ترقيم العناصر الأخرى أيضًا.

shift هذه العمليه يجب ان تفعل 3 أشياء:

  1. إزالة العنصر باستخدام الفهرس 0.
  2. انقل كل العناصر إلى اليسار, ترقيمها من الفهرس 1 الي 0, من 2 الي 1 وما الي ذالك.
  3. قم بتحديث خاصيه length .

مزيد من العناصر في المصفوفه, مزيد من الوقت لتحريكها, المزيد من العمليات في الذاكرة.

نفس الشئ يحدث مع unshift: حتي تضيف عنصر في بدايه المصفوفه, نحتاج أولاً إلى نقل العناصر الموجودة إلى اليمين, زياده ترقيمهم لدي الفهرس.

وماذا مع الوسائل push/pop? لا يحتاجون لتحريك أي شيء. حتي تستخلص عنصر من النهايه, pop هذه الوسيله تمسح الفهرس وتقلل من الطول length.

pop الإجراءت التشغليه لهذه الوسيله:

fruits.pop(); // تأخذ عنصر واحد من النهايه

** pop لاتحتاج هذه الوسيله الي نقل أي شئ, لان العناصر الاخري تحتفظ بفهارسها. هذا هو السبب في أنها سريعه للغايه.**

نفس الشئ يحدث مع الوسيلهpush .

الحلقات التكراريه

واحده من اقدم الطرق لتكرار لستخدام عناصر المصفوفه هي الحلقه for عبر الفهارس:

let arr = ["الكمثري", "البرتقال", "التفاح"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

ولكن بالنسبة للمصفوفات ، هناك شكل آخر من أشكال الحلقات, for..of:

let fruits = ["البرقوق", "البرتقال", "التفاح"];

// يتكرر عبر عناصر المصفوفه
for (let fruit of fruits) {
  alert( fruit );
}

The for..of لا يمنح الوصول إلى رقم العنصر الحالي, فقط قيمته ,ولكن في معظم الحالات يكون ذلك كافيًا. وهي أقصر.

من الناحية الفنية ، نظرًا لأن المصفوفات هي كائنات ، فمن الممكن أيضًا استخدامها for..in:

let arr = ["الكمثري", "البرتقال", "التفاح"];

for (let key in arr) {
  alert( arr[key] ); // الكمثري, البرتقال, التفاح
}

لكن هذه في الواقع فكرة سيئة. هناك مشاكل محتملة معها:

  1. تتكرر الحلقة for ... in على * جميع الخصائص * ، وليس فقط الخصائص الرقمية.

    هناك ما يسمى بكائنات “مثل المصفوفة” في المتصفح وفي بيئات أخرى, انها تبدوا مثل المصفوفات. أي ، لديهم length ولديهم خصائص الفهرس, ولكن قد يكون لديهم أيضًا خصائص وسائل غير رقمية أخرى, التي لا نحتاجها عادةً. for..in هذه الحلقه سوف ترتبهم بالرغم من ذلك. لذا إذا احتجنا للعمل مع كائنات تشبه المصفوفة ، فقد تصبح هذه الخصائص “الإضافية” مشكلة.

  2. تم تحسين الحلقة for..in للعناصر العامة ، وليس للمصفوفات ، وبالتالي فهي أبطأ بمقدار 10-100 مرة. بالطبع ، إنها لا تزال سريعة جدًا. قد يكون التسريع مهمًا فقط في الاختناقات. ولكن لا يزال يتعين علينا أن ندرك الفرق.

بشكل عام ، لا يجب استخدام “for…in” للمصفوفات.

كلمه عن “length”

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

على سبيل المثال ، عنصر واحد بمؤشر كبير يعطي طولًا كبيرًا:

let fruits = [];
fruits[123] = "التفاح";

alert( fruits.length ); // 124

لاحظ أننا عادة لا نستخدم مصفوفات من هذا القبيل.

شيء آخر مثير للاهتمام حول خاصية length هو أنه قابل للكتابة.

إذا تم تزوديها يدويًا ، فلن يحدث شيء مثير للاهتمام. ولكن إذا قللناه ، فسيتم اقتطاع المصفوفة. العملية لا رجعة فيها ، وإليك المثال:

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // يتم اقتطاعها إلى عنصرين
alert( arr ); // [1, 2]

arr.length = 5; // أعد قيمه الطول
alert( arr[3] ); // غيرمعرف: لذالك القيم لن تعد

لذا ، فإن أبسط طريقة لمسح المصفوفه هي: ;arr.length = 0.

()new Array

يوجد اكثر من طريقه لإنشاء مصفوفه:

let arr = new Array("الخ", "الكمثري", "التفاح");

نادرًا ما يتم استخدامه ، لأن الأقواس المربعة `[] أقصر. أيضا هناك ميزة صعبة معها.

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

دعونا نرى كيف يمكن للمرء أن يطلق النار على قدمه:

let arr = new Array(2); //هل سينشئ مصفوفه مكونه من [2] ?

alert( arr[0] ); // غير معرف! لا توجد عناصر.

alert( arr.length ); // الطول 2

في الكود أعلاه, مصفوفه جديده(رقم) تكون لديها كل العناصر غير معرفه.

للتهرب من هذه المفاجآت ، نستخدم عادةً الأقواس المربعة ، إلا إذا كنا نعرف حقًا ما نقوم به.

مصفوفات متعدده الأبعاد

يمكن أن تحتوي المصفوفات على عناصر عبارة عن مصفوفات أيضًا. يمكننا استخدامه للمصفوفات متعددة الأبعاد ، على سبيل المثال لتخزين المصفوفات:

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // 5, العنصر المركزي

التحويل إلي نص

المصفوفات لها تنفيذها الخاص لطريقة toString التي تُرجع قائمة من العناصر مفصولة بفواصل.

علي سبيل المثال:

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // صحيح

أيضا ، دعنا نجرب هذا:

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

لا تحتوي المصفوفات على Symbol.toPrimitive ، ولا علىvalueOf قابلة للتطبيق ، فهي تنفذ تحويل toString فقط ، لذلك هنا[] تصبح سلسلة فارغة ،[1]تصبح "" 1 "" و "[ 1،2]تصبح" 1،2 ". عندما تضيف the binaryn plus بالإضافة إلى علامة “+” فإن هذا العامل يضيف هذا الشئ إلى سلسله نصيه ، فإنه يحولها إلى سلسلة أيضًا ، لذا تبدو الخطوة التالية كما يلي:

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

الملخص

المصفوفات هو نوع خاص من الكائنات ، مناسب لتخزين وإدارة عناصر البيانات المطلوبة.

  • الإعلان:

    // الأقواس المربعة (المعتادة)
    let arr = [العنصر2, العنصر1...];
    
    // مصفوفه جديده (نادره للغايه)
    let arr = new Array(العنصر2, العنصر1...);

    يؤدي استدعاء "مصفوفه جديده (رقم) " إلى إنشاء مصفوفة بطول معين ، ولكن بدون عناصر…

  • الخاصية length هي طول المصفوفة أو ، على وجه الدقة ، آخر فهرس رقمي بالإضافة إلى واحد. يتم ضبطه تلقائيًا بواسطة طرق للمصفوفه.

  • إذا اختصرنا “الطول” يدويًا ، فسيتم اقتطاع المصفوفة.

يمكننا استخدام مصفوفة كمادة مع العمليات التالية:

  • push(...عناصر)تضيف العناصر إلى النهاية.
  • pop()إزالة العنصر من النهاية وإعادته.
  • shift() يزيل العنصر من البداية ويعيده.
  • unshift(...عناصر) تضيف العناصر إلي البدايه.

للتكرار فوق عناصر المصفوفة:

  • for (let i=0; i<arr.length; i++) --يعمل بشكل أسرع ومتوافق مع المتصفح القديم.
  • for (let item of arr) – البنية الحديثة للعناصر فقط ،
  • for (let i in arr) – لم يستعمل أبدا.

سنعود إلى المصفوفات ودراسة المزيد من الطرق لإضافة العناصر وإزالتها واستخراجها وفرز المصفوفات في الفصل توابع المصفوفات (Array methods).

مهمه

ماالذي سوف يعرضه الكود؟

let fruits = ["البرتقال", "الكمثري", "التفاح"];

// "ادفع قيمه جديده داخل"النسخ
let shoppingCart = fruits;
shoppingCart.push("الموز");

//؟ fruits ماالذي داخل
alert( fruits.length ); // ?

4:الناتج

let fruits = ["البرتقال", "الكمثري", "التفاح"];

let shoppingCart = fruits;

shoppingCart.push("الموز");

alert( fruits.length ); // 4

هذا لان المصفوفات تعتبر كائنات. لذا كلا من shoppingCart و fruits يعدوا كمرجع لنفس المصفوفه.

هيا نجرب 5 معاملات للمصفوفه.

  1. قم بانشاء عده عناصر styles “موسيقي الجاز” و “البلوز” .
  2. اضف في النهايه" موسيقي الروك آند رول"
  3. استبدل القيمة في المنتصف بـ “كلاسيكيات”. يجب ان يعمل الكود الخاص بك للعثور على القيمة الوسطى لأي مصفوفه ذات طول فردي.
  4. تجريد القيمة الأولى من مصفوفه وإظهارها.
  5. استعد Rap و Reggae الي المصفوفه .

المصفوفه في العمليه :

موسيقي الجاز, البلوز
موسيقي الجاز, البلوز, موسيقى الروك آند رول
موسيقي الجاز, كلاسيكيات, موسيقى الروك آند رول
كلاسيكيات,موسيقى الروك آند رول
موسيقى الراب, موسيقي الريغي, كلاسيكيات, موسيقى الروك آند رول
let styles = ["البلوز", "موسيقي الجاز"];
styles.push("موسيقى الروك آند رول");
styles[Math.floor((styles.length - 1) / 2)] = "كلاسيكيات";
alert( styles.shift() );
styles.unshift("موسيقي الريغي", "موسيقى الراب");

ماهي النتيجه؟ لماذا؟

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // ?

استدعاء ()arr[2] نحويا هو اسلوب جيد ()obj[method], في دور obj نحن لدينا arr, وفي دور methodنحن لدينا 2.

لذلك لدينا استدعاء للدالة arr [2] كطريقة كائن. وبطبيعة الحال ، فإنه يتلقى this يشير إلى الكائنarr ويخرج المصفوفه:

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // a,b,function(){...}

المصفوفة لها 3 قيم: في البداية كانت تحتوي على قيمتين ، بالإضافة إلى function.

اكتب الداله sumInput() التي:

  • اطلب من المستخدم القيم باستخدام prompt وتخزين تلك القيم داخل المصفوفه.
  • قم بإنهاء الاسئله عندما يدخل المستخدم قيمه غير رقمي او نص فارغ او بضغط علي “انهاء”
  • احسب وقم بإعاده عمليه الجمع لعناصر المصفوفه.

ملاحظة. الصفر 0 هو رقم صالح ، يرجى عدم إيقاف الإدخال على الصفر.

قم بتشغيل العرض التوضيحي

يرجى ملاحظة التفاصيل الدقيقة والمهمة للحل. نحن لا نقوم بتحويلvalue الي رقم فورا بعد prompt, لان بعد القيمه value = +value لن نتمكن من معرفة النص فارغ (علامة التوقف) من الصفر (رقم صالح). سنقوم بذلك لاحقًا بدلاً من ذلك.

function sumInput() {

  let numbers = [];

  while (true) {

    let value = prompt("  رقم من فضلك A Number Please", 0);

    // يجب أن نلغي؟
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert( sumInput() );

الإدخال هو مصفوفة من الأرقام ، على سبيل المثال arr = [1, -2, 3, 4, -9, 6].

المهمة هي: العثور على مصفوفة متجاورة من arr مع العدد الأقصى للعناصر.

اكتب الداله getMaxSubSum(arr) التي سوف تعيد الجمع.

علي سبيل المثال:

getMaxSubSum([-1, 2, 3, -9]) == 5 (مجموع العناصر المميزة)
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6 (خذها كلها)

إذا كانت جميع العناصر سالبة ، فهذا يعني أننا لا نأخذ أي منها (المصفوفة فارغة) ، لذا يكون المجموع صفرًا:

getMaxSubSum([-1, -2, -3]) = 0

من فضلك فكر في أسرع حل: O(n2) أو حتى O (n) إذا استطعت.

افتح sandbox بالإختبارات.

الحل الأبطئ

يمكننا حساب جميع الفئات الفرعية الممكنة.

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

علي سبيل المثال, for [-1, 2, 3, -9, 11]:

// البدء من -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// البدء من 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// البدء من 3:
3
3 + (-9)
3 + (-9) + 11

// البدء من -9
-9
-9 + 11

// البدء من 11
11

الكود هو في الواقع حلقة متداخلة: الحلقة الخارجية فوق عناصر المصفوفه ، والعد الداخلي يحسب الفئات الفرعية التي تبدأ بالعنصر الحالي.

function getMaxSubSum(arr) {
  let maxSum = 0; // إذا لم نأخذ أي عناصر ، فسيتم إرجاع الصفر

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

الحل له تعقيد زمني O(n2). بمعنى آخر ، إذا قمنا بزيادة حجم المصفوفه مرتين ، فستعمل الخوارزمية لفترة أطول 4 مرات. بالنسبة للمصفوفات الكبيرة (1000 أو 10000 أو أكثر من العناصر) ، يمكن أن تؤدي هذه الخوارزميات إلى بطء خطير.

الحل الأسرع

دعنا نسير في المصفوفة ونحتفظ بالمجموع الجزئي الحالي للعناصر في المتغير s. إذا أصبحت s سالبة في وقت ما ، قم بتعيينs = 0. سيكون الحد الأقصى لكل هذه الإجابات هو الإجابة.

إذا كان الوصف غامضًا جدًا ، فيرجى الاطلاع على الكود ، فهو قصير بما يكفي:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // لكل عنصر في المصفوفه
    partialSum += item; // أضفه إلى مجموع الجزئي
    maxSum = Math.max(maxSum, partialSum); // تذكر الحد الأقصى
    if (partialSum < 0) partialSum = 0; // صفر إذا كانت سلبية
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

تتطلب الخوارزمية تمريراً مصفوفه واحده ، لذا فإن تعقيد الوقت هو O (n).

يمكنك العثور على مزيد من المعلومات التفصيلية حول الخوارزمية هنا: Maximum subarray problem. إذا كان لا يزال من غير الواضح سبب نجاح ذلك ، فالرجاء تتبع الخوارزمية في الأمثلة أعلاه ، ومعرفة كيفية عملها ، وهذا أفضل من أي كلمات.

افتح الحل الإختبارات في sandbox.

خريطة الدورة التعليمية

التعليقات

إقرأ هذا قبل أن تضع تعليقًا…
  • إذا كان لديك اقتراحات أو تريد تحسينًا - من فضلك من فضلك إفتح موضوعًا فى جيتهاب أو شارك بنفسك بدلًا من التعليقات.
  • إذا لم تستطع أن تفهم شيئّا فى المقال - وضّح ماهو.
  • إذا كنت تريد عرض كود استخدم عنصر <code> ، وللكثير من السطور استخدم <pre>، ولأكثر من 10 سطور استخدم (plnkr, JSBin, codepen…)