గరిష్ట సుబారే లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ ByteDance సిస్కో <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ JP మోర్గాన్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ పేపాల్ Paytm ఉబెర్
అర్రే విభజించు పాలించు డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

పూర్ణాంక శ్రేణి సంఖ్యలను ఇచ్చినట్లయితే, ఆనుకొని ఉండండి subarray (కనీసం ఒక సంఖ్యను కలిగి ఉంటుంది) ఇది అతిపెద్ద మొత్తాన్ని కలిగి ఉంటుంది మరియు దాని మొత్తాన్ని తిరిగి ఇస్తుంది.

ఉదాహరణ

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

వివరణ:

[4, -1,2,1] అతిపెద్ద మొత్తం = 6 కలిగి ఉంది.

nums = [-1]
-1

అప్రోచ్ 1 (విభజించి జయించండి)

ఈ విధానంలో మేము ఈ సమస్యను పరిష్కరించడానికి విభజన మరియు జయించే సాంకేతికత గురించి చర్చిస్తాము. మేము గరిష్ట మొత్తాన్ని కలిగి ఉన్న ఆ సబార్రేను కనుగొనడానికి ప్రయత్నిస్తున్నాము. కాబట్టి వాంఛనీయ సబ్‌రే శ్రేణిలోని ఏ భాగానైనా ఉండవచ్చని మేము చెప్పగలం. కాబట్టి మేము అన్ని అవకాశాలను కవర్ చేసే మూడు కేసులను చేస్తాము:

కేసు XX:
శ్రేణి యొక్క ఎడమ భాగంలో మాక్స్ సబ్‌రే పూర్తిగా ఉంది.
కేసు XX:
మాక్స్ సబ్రేరే శ్రేణి యొక్క కుడి భాగంలో పూర్తిగా ఉంది.
కేసు XX:
మాక్స్ సబ్‌రే యొక్క పాక్షిక భాగం ఎడమ భాగంలో ఉంటుంది మరియు దాని యొక్క మరొక పాక్షిక భాగం రెండవ భాగంలో ఉంటుంది (అనగా సబ్‌రే అర్రే యొక్క మధ్య మూలకాన్ని దాటుతుంది)

కేసు 1 మరియు కేసు 2 ప్రాథమికంగా N / 2 పరిమాణ శ్రేణి యొక్క ఉపప్రాబ్లమ్, ప్రధాన సమస్య వలె అదే నిర్వచనాన్ని కలిగి ఉంటుంది. N అనేది ప్రస్తుత శ్రేణి యొక్క పరిమాణం. కాబట్టి మనం సరళంగా చేయవచ్చు పునరావృతమవుతుంది శ్రేణి యొక్క రెండు భాగాలపై ఫంక్షన్.
ఇప్పుడు ప్రధాన భాగం కేసు 3, ఇది ప్రస్తుత ఫంక్షన్‌లో మనం పరిష్కరించుకోవాలి మరియు ఈ 3 కేసులలో గరిష్ట మొత్తాన్ని తిరిగి ఇవ్వవచ్చు.

కేసు 3 కోసం మేము ఎలా పరిష్కరించగలమో చూద్దాం:

మనకు శ్రేణి = [-2,1, -3,4, -1,2,1, -5,4]
మిడ్ ఇండెక్స్‌ను రెండు సమాన భాగాలుగా విభజించడానికి మేము కనుగొన్నాము.
మధ్య సూచిక = (0 + 9) / 2 = 4

గరిష్ట సుబారే లీట్‌కోడ్ పరిష్కారం

కేసు 3 ప్రకారం, గరిష్ట మొత్తం మధ్య మూలకాన్ని దాటుతుంది. కాబట్టి మేము గరిష్ట మొత్తాన్ని మధ్యలో ప్రారంభించి ఎడమ వైపున ముగుస్తుంది. అదేవిధంగా మేము గరిష్ట మొత్తాన్ని (మధ్య + 1) ప్రారంభించి కుడి వైపున ముగుస్తుంది. ఈ విధంగా మేము కేసు 3 కోసం మధ్య సరిహద్దును దాటిన మాక్స్ సబ్‌రేను కనుగొంటాము.

అల్గోరిథం:

  • శ్రేణిని రెండు భాగాలుగా విభజించండి.
  • ఎడమ సబ్‌రే కోసం గరిష్ట సబ్‌రే మొత్తాన్ని పునరావృతంగా కనుగొనండి.
  • కుడి సబ్‌రే కోసం గరిష్ట సబ్‌రే మొత్తాన్ని పునరావృతంగా కనుగొనండి.
  • మధ్య బిందువును దాటిన గరిష్ట సబ్‌రే మొత్తాన్ని కనుగొనండి.
  • పైన పేర్కొన్న మూడు మొత్తాలను గరిష్టంగా తిరిగి ఇవ్వండి.

గరిష్ట సుబారే లీట్‌కోడ్ పరిష్కారం కోసం అమలు

సి ++ ప్రోగ్రామ్

#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 పరిమాణంలో విభజిస్తోంది. అందువల్ల పునరావృత యొక్క లోతైన స్థాయి logN అవుతుంది, ఇక్కడ శ్రేణి పరిమాణం 1 ఉంటుంది మరియు మేము అక్కడ నుండి తిరిగి వస్తున్నాము. ప్రతి స్థాయిలో మేము O (n) పనిని చేస్తున్నాము, కాబట్టి మొత్తం సమయ సంక్లిష్టత O (NlogN) అవుతుంది. ఇక్కడ పునరావృత సంబంధం ఉంది

అంతరిక్ష సంక్లిష్టత 

O (logN): 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

గరిష్ట సుబారే లీట్‌కోడ్ పరిష్కారం కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) : ఇది శ్రేణిపై ఒక పాస్ అల్గోరిథం కాబట్టి.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): అదనపు మెమరీ ఉపయోగించబడదు.