١٥ ديسمبر ٢٠٢١

المصفوفات

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

ولكن في كثير من الأحيان نجد أننا بحاجة إلى مجموعة مرتبة, حيث لدينا عنصر الأول والثاني والثالث وما إلى ذلك. علي سبيل المثال, نحن نحتاج الي تخزين مجموعه من الشياء: مسخدمين, بضائع, عناصر 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 كائن, بينما الارقام تستخدم كمفاتيح.

Remember, there are only eight basic data types in JavaScript (see the Data types chapter for more info). Array is an object and thus behaves like an object.

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

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

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

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

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

…But what makes arrays really special is their internal representation. The engine tries to store its elements in the contiguous memory area, one after another, just as depicted on the illustrations in this chapter, and there are other optimizations as well, to make arrays work really fast.

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

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

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"

Don’t compare arrays with ==

Arrays in JavaScript, unlike some other programming languages, shouldn’t be compared with operator ==.

This operator has no special treatment for arrays, it works with them as with any objects.

Let’s recall the rules:

  • Two objects are equal == only if they’re references to the same object.
  • If one of the arguments of == is an object, and the other one is a primitive, then the object gets converted to primitive, as explained in the chapter تحويل الكائنات إلى قيم مفرده.
  • …With an exception of null and undefined that equal == each other and nothing else.

The strict comparison === is even simpler, as it doesn’t convert types.

So, if we compare arrays with ==, they are never the same, unless we compare two variables that reference exactly the same array.

For example:

alert( [] == [] ); // false
alert( [0] == [0] ); // false

These arrays are technically different objects. So they aren’t equal. The == operator doesn’t do item-by-item comparison.

Comparison with primitives may give seemingly strange results as well:

alert( 0 == [] ); // true

alert('0' == [] ); // false

Here, in both cases, we compare a primitive with an array object. So the array [] gets converted to primitive for the purpose of comparison and becomes an empty string ''.

Then the comparison process goes on with the primitives, as described in the chapter نوع التحويلات:

// after [] was converted to ''
alert( 0 == '' ); // true, as '' becomes converted to number 0

alert('0' == '' ); // false, no type conversion, different strings

So, how to compare arrays?

That’s simple: don’t use the == operator. Instead, compare them item-by-item in a loop or using iteration methods explained in the next chapter.

Summary

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

  • الإعلان:

    // الأقواس المربعة (المعتادة)
    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) – لم يستعمل أبدا.

To compare arrays, don’t use the == operator (as well as >, < and others), as they have no special treatment for arrays. They handle them as any objects, and it’s not what we usually want.

Instead you can use for..of loop to compare arrays item-by-item.

We will continue with arrays and study more methods to add, remove, extract elements and sort arrays in the next chapter توابع المصفوفات (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

The solution has a time complexity of O(n2). In other words, if we increase the array size 2 times, the algorithm will work 4 times longer.

الحل الأسرع

دعنا نسير في المصفوفة ونحتفظ بالمجموع الجزئي الحالي للعناصر في المتغير 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…)