الحد الأقصى لحل Leetcode Subarray


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ ByteDance سيسكو فيسبوك جولدمان ساكس جوجل جي بي مورغان لينكد إن: Microsoft أوراكل Paypal Paytm اوبر
مجموعة فرق تسد البرمجة الديناميكية

المشكلة بيان

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

مثال

nums = [-2,1,-3,4,-1,2,1,-5,4]
6

التفسير:

[4، -1,2,1،6،XNUMX] لديها أكبر مجموع = XNUMX.

nums = [-1]
-1

النهج 1 (فرق تسد)

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

حالة 1:
يقع Max subarray بالكامل في النصف الأيسر من المصفوفة.
حالة 2:
يقع Max subarray تمامًا في النصف الأيمن من المصفوفة.
حالة 3:
يقع الجزء الجزئي من المصفوفة الفرعية القصوى في النصف الأيسر ويوجد جزء جزئي آخر منه في النصف الثاني (أي أن المصفوفة الفرعية تتخطى العنصر الأوسط من المصفوفة)

كما يمكننا أن نرى الحالة 1 والحالة 2 هي في الأساس مشكلة فرعية لمصفوفة بحجم N / 2 لها نفس تعريف المشكلة الرئيسية. حيث N هو حجم المصفوفة الحالية. لذلك يمكننا ببساطة يتكرر الدالة على نصفي المصفوفة.
الآن الجزء الرئيسي هو الحالة 3 والتي يتعين علينا حلها في الوظيفة الحالية ومن ثم يمكننا إرجاع أقصى مجموع من هذه الحالات الثلاث.

لنرى كيف يمكننا حل الحالة 3:

لنفترض أن لدينا مصفوفة = [-2,1،3,4، -1,2,1،5,4، -XNUMX،XNUMX،XNUMX، -XNUMX،XNUMX]
نجد مؤشرًا متوسطًا لنقسمه إلى نصفين متساويين.
الفهرس المتوسط ​​= (0 + 9) / 2 = 4

الحد الأقصى لحل Leetcode Subarray

كما تشير الحالة 3 إلى أن الحد الأقصى للمبلغ سيتخطى العنصر الأوسط. لذا سنحاول إيجاد أقصى مجموع يبدأ من المنتصف وينتهي عند الجانب الأيسر. وبالمثل ، سنجد أقصى مجموع يبدأ عند (منتصف + 1) وينتهي عند الجانب الأيمن. بهذه الطريقة سنجد المصفوفة الفرعية القصوى التي تعبر الحد الأوسط للحالة 3.

الخوارزمية:

  • قسّم المصفوفة إلى نصفين.
  • ابحث بشكل متكرر عن الحد الأقصى لمجموع المصفوفة الفرعية للصفيف الفرعي الأيسر.
  • ابحث بشكل متكرر عن الحد الأقصى لمجموع المصفوفة الفرعية للمصفوفة الفرعية اليمنى.
  • أوجد الحد الأقصى لمجموع المصفوفة الفرعية الذي يتجاوز نقطة المنتصف.
  • إرجاع الحد الأقصى من المبالغ الثلاثة أعلاه.

تنفيذ الحد الأقصى لحل Leetcode Subarray

برنامج C ++

#include <bits/stdc++.h>
using namespace std;

int helper(int i,int j, vector<int>& nums)
{
    if(i==j) return nums[i];
    int left_cross=INT_MIN, right_cross=INT_MIN;

    int mid= (i+j)/2;
    int cur=0;
    for(int k=mid+1;k<=j;k++)
    {
        cur+= nums[k];
        right_cross= max(right_cross,cur);
    }

    cur=0;
    for(int k=mid;k>=i;k--)
    {
        cur+= nums[k];
        left_cross= max(left_cross,cur);
    }

    int cross_sum = left_cross + right_cross;
    int left_sum  = helper(i,mid,nums);
    int right_sum = helper(mid+1,j,nums);

    return max( cross_sum , max(left_sum , right_sum) );
}

int maxSubArray(vector<int>& nums) {
    return helper(0,nums.size()-1,nums);
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

برنامج جافا

class Rextester{
    
  static int helper(int i,int j, int[] nums)
    { 
        if(i==j) return nums[i];       
        int left_cross=Integer.MIN_VALUE, right_cross=Integer.MIN_VALUE;
        
        int mid= (i+j)/2;
        int cur=0;
        for(int k=mid+1;k<=j;k++)
        {
            cur+= nums[k];
            right_cross= Math.max(right_cross,cur);
        }
        
        cur=0;
        for(int k=mid;k>=i;k--)
        {
            cur+= nums[k];
            left_cross= Math.max(left_cross,cur);
        }
        
        int cross_sum=  left_cross + right_cross; 
        int left_sum = helper(i,mid,nums);
        int right_sum = helper(mid+1,j,nums);
        
        return Math.max( cross_sum , Math.max(left_sum , right_sum) );        
    }
    
    public static int maxSubArray(int[] nums) {
        return helper(0,nums.length-1,nums);
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

تحليل التعقيد لأقصى حل Leetcode Subarray

تعقيد الوقت

O (NlogN): في الواقع ، نقسم المشكلة إلى نصفين متساويين بالحجم N / 2. مرة أخرى يتم القسمة في الحجم N / 4 وهكذا. ومن ثم سيكون أعمق مستوى من العودية هو logN حيث سيكون حجم المصفوفة 1 ونحن نعود من هناك. في كل مستوى نقوم بمهمة O (n) ومن ثم سيكون التعقيد الزمني الإجمالي O (NlogN). هنا علاقة التكرار

تعقيد الفضاء 

O (تسجيل N): يتم استخدام مساحة تسجيل الدخول لمكدس العودية.

 

المقاربة 2 (طريقة كادان)

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

الخوارزمية:

  • إنشاء متغير لتخزين الحد الأقصى العالمي. بدء بأكبر رقم سالب (INT_MIN).
  • إنشاء متغير لتخزين المبلغ الحالي. بدء بصفر.
  • قم بتشغيل حلقة من اليسار إلى اليمين عبر المصفوفة. إذا أصبح المجموع الحالي سالبًا ، فقم بتحديثه بالقيمة 0.
  • أضف العنصر الحالي إلى المجموع الحالي وقم بتحديث الحد الأقصى العام إذا كان المجموع الحالي أكبر من الحد الأقصى العام.
  • إرجاع الحد الأقصى العالمي.

تنفيذ الحد الأقصى لحل Leetcode Subarray

برنامج C ++

#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) 
{
    int max_sum=INT_MIN;
    int cur=0;
    for(auto x:nums)
    {
        if(cur<0) cur=0;
        cur += x;
        max_sum =  max(max_sum , cur);
    }
    return max_sum;
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

برنامج جافا

class Rextester{
  
    public static int maxSubArray(int[] nums) 
    {
        int max_sum = Integer.MIN_VALUE;
        int cur=0;
        for(int x:nums)
        {
            if(cur<0) cur=0;
            cur += x;
            max_sum =  Math.max(max_sum , cur);
        }
        return max_sum;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

تحليل التعقيد لأقصى حل Leetcode Subarray

تعقيد الوقت

على) : لأنها خوارزمية واحدة تمر عبر المصفوفة.

تعقيد الفضاء 

يا (1): لا يتم استخدام ذاكرة إضافية.