تمرين عن المصفوفات JavaScript حساب أكبر مجموع جزئي متتالي في مصفوفة

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

على سبيل المثال ، بالنسبة إلى [-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 + (-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;
}

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

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

 ما رأيكم في هذا الحل 

صورت الكود لانني لم استطع ان ارفعه على شكل كود ما المشكلة ؟

arr1,arr2,arr3 هي مصفوفات اجرب عليها 

هذه الطريقة اعرف انها معقدة وغبية وذالك لانني حقا مبتدا واريد التعلم فلاتبخلوا علينا بالتوجيه و

let arr2 = [1, -8, 6, -4, 22, 3, -5, 4, -8, 7, 1, -17]

6+(-4)+22+3 =27

لتحليل هاته الخوارزمية قمت بالعمل التالي : 

1 - إيجاد كل المصفوفات الفرعية التي يمكن تشكيلها من عنصر فأكثر من عناصر المصفوفة الأصلية .

2 - حساب مجموع أعداد كل مصفوفة فرعية . و أيضا لا يجب أن ننسى مجموع كل المجموعات الفرعية التي يمكن تشكيلها من هاته المجموعة الفرعية (قد تبدوا الفكرة معقدة لكن ينبغي تبسيطها و فهم أيضا أنه يمكن معاملة المجموعة الفرعية على أنها مجموعة أصلية غير محسوب مجموعها بعد و قد يحتوي مجموع إحداها على المجموع المطلوب فلا ينبغي أبدا إغفالها ).

3 - في كل دورة لحساب المجاميع يتم تسجيل هذا المجموع , و لا داعي لتسجيله إن كان محصلا بالفعل من عدد n عناصر من قبل .

3 - الان و قد تم حساب كل المجاميع الممكنة , يجب أخذ أكبرها قيمة و فقط .

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

بالنسبة للكود سيكون مشابها لما يطبق نفس المنطق , و قد قمت بكتابته على هذا النحو : 

1. إنشاء دالة تتولى الخطوة 2 و 1 معا , بحيث تقوم بإيجاد المصفوفات الفرعية و المصفوفات الفرعية الممكن تشكيلها من هاته المصفوفة الفرعية و هكذا . و كل مرة يتم تشكيل مصفوفة فرعية يتم تسجيل مجموع عناصرها :

var sums = []; // تحضير مصفوفة مجاميع فارغة

function getAllPossibleSums(group, sub_group)
{
    // 
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        // لا حاجة لتسجيل مجموع في بداية الدور وفي حال عدم وجود أي مصفوفة
        if( group.length > 0 ){

            // حساب المجموع
            var total = group.reduce(function(a,b){return a+b;},0);
            
            // لا حاجة لتسجيل المجموع إلا إن كان غير مسجل
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }

    // بداية التكرار تكون هنا
    else{
       // ايجاد و تسجيل مجموع كل العناصر
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       // ايجاد وتسجيل مجموع كل العناصر الممكن تشكيلها من المصفوفة الفرعية
       getAllPossibleSums(group,sub_group.slice(1));
    }
  
    // إعادة المجاميع 
    return sums;

}

     2. عمل دالة تقوم بالخطوة رقم 3 : 

function getMaxNumInArray(arr){
    let i;

    // البدء بالعنصر الأول
    let max = arr[0];

    //  اجتياز العناصر بعد الاندكس المختار ومقارنة كل عنصر مع العنصر المختار
    for (i = 1; i < arr.length; i++) {
        // في حالة وجود قيمة أكبر سجلها
        if (arr[i] > max){
          max = arr[i];
        }
    }
    
    // إعادة أكبر عنصر
    return max;
}

    3. عمل دالة تلخص عمل الماضيتين : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

ثم أخيرا دمج الأكواد على هذا النحو : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

var sums = [];
/**
* هاته الدالة تقوم بتلخيص منطق العملية
* @param arr : array  
*/
function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNum(all);   
}

/**
* هاته الدالة تقوم بتسجيل أي مجموع يمكن تشيكله من المصفوفة
* @param group : array , sub_group: array
*/
function getAllPossibleSums(group, sub_group)
{
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        if( group.length > 0 ){

            var total = group.reduce(function(a,b){return a+b;},0);
            
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }
 
    else{
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       getAllPossibleSums(group,sub_group.slice(1));
    }
    
    return sums;
}

/**
* إيجاد العدد اﻷكبر قيمة في قائمة أعداد
* @param arr : array
*/
function getMaxNumInArr(arr){
    let i;

    let max = arr[0];

    for (i = 1; i < arr.length; i++) {
        if (arr[i] > max){
            max = arr[i];
        }
    }
      
    return max;
}

و من ثم إستدعاء الدالة على هذا النحو : 

var arr = [ 1, -2,  3,  4,  -9,  6];

console.log(getMaxSubSum(arr)); // 14 

بتاريخ 45 دقائق مضت قال Adnane Kadri:

لتحليل هاته الخوارزمية قمت بالعمل التالي : 

1 - إيجاد كل المصفوفات الفرعية التي يمكن تشكيلها من عنصر فأكثر من عناصر المصفوفة الأصلية .

2 - حساب مجموع أعداد كل مصفوفة فرعية . و أيضا لا يجب أن ننسى مجموع كل المجموعات الفرعية التي يمكن تشكيلها من هاته المجموعة الفرعية (قد تبدوا الفكرة معقدة لكن ينبغي تبسيطها و فهم أيضا أنه يمكن معاملة المجموعة الفرعية على أنها مجموعة أصلية غير محسوب مجموعها بعد و قد يحتوي مجموع إحداها على المجموع المطلوب فلا ينبغي أبدا إغفالها ).

3 - في كل دورة لحساب المجاميع يتم تسجيل هذا المجموع , و لا داعي لتسجيله إن كان محصلا بالفعل من عدد n عناصر من قبل .

3 - الان و قد تم حساب كل المجاميع الممكنة , يجب أخذ أكبرها قيمة و فقط .

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

بالنسبة للكود سيكون مشابها لما يطبق نفس المنطق , و قد قمت بكتابته على هذا النحو : 

1. إنشاء دالة تتولى الخطوة 2 و 1 معا , بحيث تقوم بإيجاد المصفوفات الفرعية و المصفوفات الفرعية الممكن تشكيلها من هاته المصفوفة الفرعية و هكذا . و كل مرة يتم تشكيل مصفوفة فرعية يتم تسجيل مجموع عناصرها :

var sums = []; // تحضير مصفوفة مجاميع فارغة

function getAllPossibleSums(group, sub_group)
{
    // 
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        // لا حاجة لتسجيل مجموع في بداية الدور وفي حال عدم وجود أي مصفوفة
        if( group.length > 0 ){

            // حساب المجموع
            var total = group.reduce(function(a,b){return a+b;},0);
            
            // لا حاجة لتسجيل المجموع إلا إن كان غير مسجل
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }

    // بداية التكرار تكون هنا
    else{
       // ايجاد و تسجيل مجموع كل العناصر
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       // ايجاد وتسجيل مجموع كل العناصر الممكن تشكيلها من المصفوفة الفرعية
       getAllPossibleSums(group,sub_group.slice(1));
    }
  
    // إعادة المجاميع 
    return sums;

}

     2. عمل دالة تقوم بالخطوة رقم 3 : 

function getMaxNumInArray(arr){
    let i;

    // البدء بالعنصر الأول
    let max = arr[0];

    //  اجتياز العناصر بعد الاندكس المختار ومقارنة كل عنصر مع العنصر المختار
    for (i = 1; i < arr.length; i++) {
        // في حالة وجود قيمة أكبر سجلها
        if (arr[i] > max){
          max = arr[i];
        }
    }
    
    // إعادة أكبر عنصر
    return max;
}

    3. عمل دالة تلخص عمل الماضيتين : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

ثم أخيرا دمج الأكواد على هذا النحو : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

var sums = [];
/**
* هاته الدالة تقوم بتلخيص منطق العملية
* @param arr : array  
*/
function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNum(all);   
}

/**
* هاته الدالة تقوم بتسجيل أي مجموع يمكن تشيكله من المصفوفة
* @param group : array , sub_group: array
*/
function getAllPossibleSums(group, sub_group)
{
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        if( group.length > 0 ){

            var total = group.reduce(function(a,b){return a+b;},0);
            
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }
 
    else{
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       getAllPossibleSums(group,sub_group.slice(1));
    }
    
    return sums;
}

/**
* إيجاد العدد اﻷكبر قيمة في قائمة أعداد
* @param arr : array
*/
function getMaxNumInArr(arr){
    let i;

    let max = arr[0];

    for (i = 1; i < arr.length; i++) {
        if (arr[i] > max){
            max = arr[i];
        }
    }
      
    return max;
}

و من ثم إستدعاء الدالة على هذا النحو : 

var arr = [ 1, -2,  3,  4,  -9,  6];

console.log(getMaxSubSum(arr)); // 14 

يمكنك تجربة الكود هنا .

بتاريخ 5 ساعات قال Adnane Kadri:

لتحليل هاته الخوارزمية قمت بالعمل التالي : 

1 - إيجاد كل المصفوفات الفرعية التي يمكن تشكيلها من عنصر فأكثر من عناصر المصفوفة الأصلية .

2 - حساب مجموع أعداد كل مصفوفة فرعية . و أيضا لا يجب أن ننسى مجموع كل المجموعات الفرعية التي يمكن تشكيلها من هاته المجموعة الفرعية (قد تبدوا الفكرة معقدة لكن ينبغي تبسيطها و فهم أيضا أنه يمكن معاملة المجموعة الفرعية على أنها مجموعة أصلية غير محسوب مجموعها بعد و قد يحتوي مجموع إحداها على المجموع المطلوب فلا ينبغي أبدا إغفالها ).

3 - في كل دورة لحساب المجاميع يتم تسجيل هذا المجموع , و لا داعي لتسجيله إن كان محصلا بالفعل من عدد n عناصر من قبل .

3 - الان و قد تم حساب كل المجاميع الممكنة , يجب أخذ أكبرها قيمة و فقط .

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

بالنسبة للكود سيكون مشابها لما يطبق نفس المنطق , و قد قمت بكتابته على هذا النحو : 

1. إنشاء دالة تتولى الخطوة 2 و 1 معا , بحيث تقوم بإيجاد المصفوفات الفرعية و المصفوفات الفرعية الممكن تشكيلها من هاته المصفوفة الفرعية و هكذا . و كل مرة يتم تشكيل مصفوفة فرعية يتم تسجيل مجموع عناصرها :

var sums = []; // تحضير مصفوفة مجاميع فارغة

function getAllPossibleSums(group, sub_group)
{
    // 
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        // لا حاجة لتسجيل مجموع في بداية الدور وفي حال عدم وجود أي مصفوفة
        if( group.length > 0 ){

            // حساب المجموع
            var total = group.reduce(function(a,b){return a+b;},0);
            
            // لا حاجة لتسجيل المجموع إلا إن كان غير مسجل
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }

    // بداية التكرار تكون هنا
    else{
       // ايجاد و تسجيل مجموع كل العناصر
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       // ايجاد وتسجيل مجموع كل العناصر الممكن تشكيلها من المصفوفة الفرعية
       getAllPossibleSums(group,sub_group.slice(1));
    }
  
    // إعادة المجاميع 
    return sums;

}

     2. عمل دالة تقوم بالخطوة رقم 3 : 

function getMaxNumInArray(arr){
    let i;

    // البدء بالعنصر الأول
    let max = arr[0];

    //  اجتياز العناصر بعد الاندكس المختار ومقارنة كل عنصر مع العنصر المختار
    for (i = 1; i < arr.length; i++) {
        // في حالة وجود قيمة أكبر سجلها
        if (arr[i] > max){
          max = arr[i];
        }
    }
    
    // إعادة أكبر عنصر
    return max;
}

    3. عمل دالة تلخص عمل الماضيتين : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

ثم أخيرا دمج الأكواد على هذا النحو : 

function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNumInArr(all);   
}

var sums = [];
/**
* هاته الدالة تقوم بتلخيص منطق العملية
* @param arr : array  
*/
function getMaxSubSum(arr)
{
    var all = getAllPossibleSums([],arr);

    return getMaxNum(all);   
}

/**
* هاته الدالة تقوم بتسجيل أي مجموع يمكن تشيكله من المصفوفة
* @param group : array , sub_group: array
*/
function getAllPossibleSums(group, sub_group)
{
    if( group.length == arr.length || (group.length <= arr.length && sub_group.length == 0) ){
        
        if( group.length > 0 ){

            var total = group.reduce(function(a,b){return a+b;},0);
            
            if(sums.indexOf(total) == -1){
                sums.push(total);
            }

        }
    }
 
    else{
       getAllPossibleSums(group.concat(sub_group[0]),sub_group.slice(1));

       getAllPossibleSums(group,sub_group.slice(1));
    }
    
    return sums;
}

/**
* إيجاد العدد اﻷكبر قيمة في قائمة أعداد
* @param arr : array
*/
function getMaxNumInArr(arr){
    let i;

    let max = arr[0];

    for (i = 1; i < arr.length; i++) {
        if (arr[i] > max){
            max = arr[i];
        }
    }
      
    return max;
}

و من ثم إستدعاء الدالة على هذا النحو : 

var arr = [ 1, -2,  3,  4,  -9,  6];

console.log(getMaxSubSum(arr)); // 14 

ولكن الخوارزمية التي وضعتها غير صحيحة فقد غفلت عن شرط التتالي كما هو في نص التمرين ,اضافة الى انك تتجاهل الاعداد السالبة , فهنا مثلا يفترض ان يكون اكبر المجموع 7 لايهم ان كان بينهم عدد سالب لا يؤثر ,في حالتنا مثلا لو كان بين 3 و 4 الرقم (-2) سيتخطى البرنامج هذا الجزء و في الاخير لايجد الا الرقم 6 الذي هو في اخر المصفوفة كابر جزء,الخوارزمية تبدا من 1 , يحفظه , ثم يضيف (-2) الخ المهم في الاخير يجب ان تتحصل على قطعة من المصفوفة بها اكبر المجموع لها اتمنى ان تكون فهمتني اليك مثالا للمصفوفة : [-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 + (-9)

3 + (-9) + 11

// بدءًا من -9

-9

-9 + 11

// ابتداء من 11

11

• لا داعِ لتشكيل جميع المصفوفات الفرعية و تخزينها في متغير لأن هذا يأخذ ذاكرة بدون داعِ يمكننا تحديد المصفوفات الجزئية بحلقتين i, j و المرور على هذه العناصر وحساب المجموع الجزئي فيها ومقارنته مع المتغير العام.
• القيمة البدائية للمتغير الذي سنخزن فيه النتيجة يجب ألا تكون 0، لأنه في حالة كانت جميع العناصر سالبة سيكون جواب المسألة خطأ لأنه سيعرض 0 بدل القيمة السالبة الأكبر ضمن عناصر المصفوفة.

لذلك إن شيفرة المدرب محمد آيت لعراك أفضل ولكن يجب تعديلها قليلا في جزئية القيمة الابتدائية لمتغير الجواب ليجلب أكبر قيمة عنصر في المصفوفة (وبهذه الحالة سيخزن مؤقتا قيمة أكبر عدد سالب في حال كانت جميع العناصر في المصفوفة سالبة) وهذا لن يؤثر في حال كان هنالك حل آخر أكبر بدون هذه الحالة الخاصة.

function getMaxSubSum(arr) {

  let maxSum = Math.max(...arr); // إذا لم نأخذ أي عناصر ، فسيتم إرجاع أكبر عدد سالب

  for (let i = 0; i < arr.length; i++) {
                                 
    let sumFixedStart = 0; // عند حساب المجموع لمصفوفة جزئية نبدأ ب 0 وهذا سليم
                                 
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

يمكنك تجريب المثال التالي:

console.log( getMaxSubSum([-1, -2, -9]) );

وسيعطي جواب -1 (أكبر قيمة سالبة)

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