زیادہ سے زیادہ سبریری لیٹ کوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ ByteDance سسکو فیس بک گولڈمین سیکس گوگل JPMorgan لنکڈ مائیکروسافٹ اوریکل پے پال پی ٹی ایم ایم Uber
لڑی تقسیم اور فتح متحرک پروگرامنگ

مسئلہ یہ بیان

ایک انٹیجر ارے نمبر دیئے گئے ، مبہم تلاش کریں subarray (کم از کم ایک عدد پر مشتمل) جس میں سب سے زیادہ رقم ہو اور اس کی رقم واپس ہوجائے۔

مثال کے طور پر

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

وضاحت:

[4 ، -1,2,1،6،XNUMX] میں سب سے زیادہ رقم = XNUMX ہے۔

nums = [-1]
-1

نقطہ نظر 1 (تقسیم اور فتح)

اس نقطہ نظر میں ہم اس مسئلے کو حل کرنے کے لئے تقسیم اور فتح کی تکنیک کے بارے میں تبادلہ خیال کریں گے۔ ہم کوشش کر رہے ہیں کہ متناسب سبری جس میں زیادہ سے زیادہ رقم ہو۔ لہذا ہم کہہ سکتے ہیں کہ زیادہ سے زیادہ سبری سرے کے کسی بھی حصے میں پڑ سکتی ہے۔ لہذا ہم تین ایسے معاملات کرتے ہیں جن میں تمام امکانات شامل ہوں گے۔

کیس 1:
میکس سبیارے صف کے بائیں نصف حصے میں مکمل طور پر مضمر ہے۔
کیس 2:
میکس سبیارے سرنی کے دائیں نصف حصے میں مکمل طور پر مضمر ہے۔
کیس 3:
زیادہ سے زیادہ سبریے کا جزوی حصہ بائیں آدھے حصے میں ہے اور اس کا ایک اور جزوی حصہ دوسرے نصف حصے میں ہے (یعنی سابری سرنی کے وسط عنصر کو عبور کررہا ہے)

جیسا کہ ہم دیکھ سکتے ہیں کہ کیس 1 اور کیس 2 بنیادی طور پر N / 2 سائز کے سر کا ایک سب پروبلم ہے جس کی بنیادی پریشانی کی طرح تعریف ہے۔ جہاں N موجودہ حجم کا سائز ہے۔ تو ہم آسانی سے کر سکتے ہیں بار بار سرنی کے دو حصوں پر کام
اب اہم حصہ کیس 3 ہے جسے ہمیں موجودہ فنکشن میں حل کرنا ہے اور پھر ہم ان 3 صورتوں میں سے زیادہ سے زیادہ رقم واپس کرسکتے ہیں۔

آئیے دیکھتے ہیں کہ ہم کیس 3 کے حل کو کس طرح حل کرسکتے ہیں۔

فرض کریں ہمارے پاس صفات ہیں [[-2,1،3,4، -1,2,1،5,4، -XNUMX،XNUMX،XNUMX، -XNUMX،XNUMX]
ہمیں وسط انڈیکس ملتا ہے تاکہ اسے دو برابر حصوں میں تقسیم کیا جاسکے۔
وسط انڈیکس = (0 + 9) / 2 = 4

زیادہ سے زیادہ سبریری لیٹ کوڈ حل

جیسا کہ کیس 3 کہہ رہا ہے کہ زیادہ سے زیادہ رقم درمیانی عنصر کو عبور کرے گی۔ لہذا ہم کوشش کریں گے کہ زیادہ سے زیادہ رقم وسط سے شروع ہوتی ہو اور اختتام بائیں جانب ہو۔ اسی طرح ہمیں زیادہ سے زیادہ رقم (وسط + 1) سے شروع ہونے اور دائیں جانب ختم ہونے کو مل جائے گی۔ اس طرح سے ہمیں زیادہ سے زیادہ سبری مل جائے گی جو کیس 3 کی درمیانی حد عبور کرتی ہے۔

الگورتھم:

  • سرنی کو دو حصوں میں تقسیم کریں۔
  • بایاں سبری کے لئے بار بار زیادہ سے زیادہ سبریری جوڑے تلاش کریں۔
  • تکرار کے ساتھ دائیں سببارے کے ل sub زیادہ سے زیادہ subarray رقم تلاش کریں۔
  • درمیانی نقطہ کو عبور کرنے والی زیادہ سے زیادہ سبری رے تلاش کریں۔
  • زیادہ سے زیادہ تین رقم جمع کرو۔

زیادہ سے زیادہ سبریری لیٹ کوڈ حل کے لئے عمل درآمد

سی ++ پروگرام

#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

زیادہ سے زیادہ سبری لیٹ کوڈ حل کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (NlogN): تقسیم اور فتح میں حقیقت میں ہم اس مسئلے کو سائز N / 2 کے دو برابر حصوں میں تقسیم کر رہے ہیں۔ ایک بار پھر یہ N / 4 اور اسی طرح کے سائز میں تقسیم ہورہا ہے۔ لہذا تکرار کی سب سے گہری سطح لاگ ان ہوگی جہاں صف کی مقدار 1 ہوگی اور ہم وہاں سے واپس جارہے ہیں۔ ہر سطح پر ہم O (n) کام کر رہے ہیں لہذا کل وقتی پیچیدگی O (NlogN) ہوگی۔ یہاں تکرار کا رشتہ ہے

خلائی پیچیدگی 

O (logN): لاگ این اسپیس کو تکرار اسٹیک کے لئے استعمال کیا جاتا ہے۔

 

نقطہ نظر 2 (کڈانے کا طریقہ)

کڈانے کا طریقہ ذیلی صف کے لئے ایک مشہور الگورتھم ہے۔ اس طریقہ کار میں ہم دیئے گئے ان پٹ سرنی پر صرف ایک بار پھر تکرار کرتے ہیں۔ ہم شروع میں ایک موجودہ رقم صفر کی قیمت کے ساتھ لیتے ہیں اور ہر عنصر کو راہ میں شامل کرتے ہیں۔ ہم ہر عنصر کو موجودہ رقم میں شامل کرتے ہیں اگر سابقہ ​​موجودہ رقم منفی نہیں ہے یا بصورت دیگر ہم محض تسلسل کو توڑتے ہیں اور موجودہ عنصر کو موجودہ عنصر کے ساتھ اپ ڈیٹ کرتے ہیں۔ اس کے ساتھ ہر مقام پر ہم یہ چیک کرتے ہیں کہ موجودہ رقم بھی عالمی زیادہ سے زیادہ ہے یا نہیں اور اس کے مطابق عالمی زیادہ سے زیادہ کو اپ ڈیٹ کریں۔

الگورتھم:

  • عالمی سطح پر زیادہ سے زیادہ ذخیرہ کرنے کے لئے متغیر بنائیں۔ سب سے زیادہ منفی نمبر (INT_MIN) کے ساتھ آغاز کریں۔
  • موجودہ رقم جمع کرنے کے لئے ایک متغیر بنائیں۔ صفر سے آغاز کریں۔
  • صف پر بائیں سے دائیں تک ایک لوپ چلائیں۔ اگر موجودہ رقم منفی ہوگئی ہے تو اسے 0 کی قیمت کے ساتھ اپ ڈیٹ کریں۔
  • موجودہ عنصر کو موجودہ رقم میں شامل کریں اور اگر موجودہ رقم عالمی زیادہ سے زیادہ سے زیادہ ہو تو عالمی سطح پر زیادہ سے زیادہ تازہ کاری کریں۔
  • زیادہ سے زیادہ عالمی لوٹائیں۔

زیادہ سے زیادہ سبریری لیٹ کوڈ حل کے لئے عمل درآمد

سی ++ پروگرام

#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

زیادہ سے زیادہ سبری لیٹ کوڈ حل کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N): چونکہ یہ صف پر ایک پاس الگورتھم ہے۔

خلائی پیچیدگی 

O (1): کوئی اضافی میموری استعمال نہیں کی جاتی ہے۔