מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג ביטעדאַנסע סיסקאָ facebook גאָלדמאַן סאַקס גוגל דזשפּמאָרגאַן לינקעדין מייקראָסאָפֿט אָראַקל פּייַפּאַל Paytm ובער
אַלגערידאַמז מענגע קאָדירונג צעטיילן און קאַנגקער דינאַמיש פּראָגראַממינג אינטערוויו interviewprep LeetCode LeetCodeSolutions

פּראָבלעם סטאַטעמענט  

מיט אַ ינטאַדזשער מענגע נומער, געפֿינען די קאַנטיגיואַס סובאַרראַי (מיט לפּחות איין נומער) וואָס האט די גרעסטע סאַכאַקל און ווייַזן זיין סומע.

בייַשפּיל

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

דערקלערונג:

[4, -1,2,1] האט די גרעסטע סומע = 6.

nums = [-1]
-1

צוגאַנג 1 (טיילן און קאָנקווער)  

אין דעם צוגאַנג, מיר וועלן דיסקוטירן וועגן צעטיילן און קאַנגקער טעכניק צו סאָלווע דעם פּראָבלעם. מיר פּרוּווט צו געפֿינען די קאַנטיגיואַס סובאַרראַי מיט אַ מאַקסימום סומע. אַזוי מיר קענען זאָגן אַז די אָפּטימום סובאַרראַי קען זיין אין קיין טייל פון די מענגע. אַזוי מיר מאַכן דריי קאַסעס וואָס וועט דעקן אַלע פּאַסאַבילאַטיז:

קאַסע קסנומקס:
מאַקס סובאַרראַי ליגט גאָר אין די לינקס האַלב פון די מענגע.
קאַסע קסנומקס:
מאַקס סובאַרראַי ליגט גאָר אין די רעכט האַלב פון די מענגע.
קאַסע קסנומקס:
אַ טייל פון די מאַקסימום סובאַרראַי ליגט אין די לינקס האַלב און אן אנדער פּאַרטיייש טייל פון אים ליגט אין די רגע האַלב (די סובאַרראַי איז אַריבער די מיטל עלעמענט פון דער מענגע)

ווי מיר קענען זען קאַסע 1 און קאַסע 2 איז בייסיקלי אַ סאַב-פּראָבלעם פון N / 2 סייזד מענגע מיט דער זעלביקער דעפֿיניציע ווי דער הויפּט פּראָבלעם. וווּ N איז די גרייס פון דעם קראַנט מענגע. אַזוי מיר קענען פשוט רעקורס די פונקציע איבער צוויי כאַווז פון די מענגע.
איצט דער הויפּט טייל איז פאַל 3 וואָס מיר האָבן צו סאָלווע אין די קראַנט פונקציע און מיר קענען צוריקקומען די מאַקסימום סומע פון ​​די 3 קאַסעס.

זע אויך
נומער פון סיבלינגז פֿאַר אַ געגעבן נאָדע אין דער טרי בוים

לאָמיר זען ווי מיר קענען סאָלווע פֿאַר פאַל 3:

רעכן מיר האָבן מענגע = [-2,1, -3,4, -1,2,1, -5,4]
מיר געפֿינען מיטן אינדעקס צו טיילן עס אין צוויי גלייַך כאַווז.
מיטן אינדעקס = (0 + 9) / 2 = 4

מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן

אין פאַל 3, די מאַקסימום סומע וועט אַריבער די מיטל עלעמענט. דעריבער, מיר וועלן פּרובירן צו געפֿינען די מאַקסימום סומע סטאַרטינג בייַ מיטן און ענדיקן ביי די לינקס זייַט. סימילאַרלי, מיר וועלן געפֿינען די מאַקסימום סומע סטאַרטינג בייַ (מיטן 1) און ענדיקן אויף די רעכט זייַט. אין דעם וועג, מיר וועלן געפֿינען די מאַקסימום סאַבסטרייט וואָס איז אַריבער די מיטל גרענעץ פֿאַר פאַל 3.

אַלגערידאַם:

  • טיילן די מענגע אין צוויי כאַווז.
  • רעקורסיוועלי געפֿינען די מאַקסימום סאַבאַריי סומע פֿאַר לינקס סאַבאַריי.
  • רעקורסיוועלי געפֿינען די מאַקסימום סאַבאַריי סומע פֿאַר רעכט סאַבאַריי.
  • געפֿינען די מאַקסימום סומע וואָס איז אַריבער די מיטל.
  • ווייַזן די מאַקסימום פון דריי סאַמז.

ימפּלאַמענטיישאַן פֿאַר מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (NlogN): אין צעטיילונג און קאַנגקער אַקשלי, דיוויד די פּראָבלעם אין צוויי גלייַך כאַווז פון גרייס N / 2. ווידער עס איז דיוויידינג אין גרייס פון N / 4 און אַזוי אויף. דערפֿאַר די דיפּאַסט מדרגה פון רעקורסיאָן וועט זיין לאָגד ווו די גרייס פון די מענגע וועט זיין 1 און מיר זענען אומגעקערט פֿון דאָרט. אין יעדער מדרגה מיר טאָן די O (n) אַרבעט, אַזוי די גאַנץ צייט קאַמפּלעקסיטי וועט זיין O (NlogN). דאָ די ריקעראַנס באַציונג איז

זע אויך
לייג און זוך וואָרט - דאַטן סטרוקטור פּלאַן לעעטקאָדע

ספעיס קאַמפּלעקסיטי 

אָ (לאָגן): לאָגן פּלאַץ איז געניצט פֿאַר רעקורסיאָן אָנלייגן.

 

צוגאַנג 2 (Kadane ס אופֿן)  

די מעטאַד פון Kadane איז אַ באַרימט אַלגערידאַם פֿאַר סאַב. אין דעם אופֿן מיר נאָר יבערקערן אַמאָל איבער די געגעבן ינפּוט מענגע. מיר נעמען אַ קראַנט סומע ערשט מיט ווערט נול און לייגן יעדער עלעמענט אין דעם וועג. מיר לייגן יעדער עלעמענט צו די קראַנט סומע אויב די פריערדיקע קראַנט סומע איז נישט נעגאַטיוו אָדער אַנדערש מיר נאָר ברעכן די העמשעכדיקייַט און דערהייַנטיקן די קראַנט סומע מיט קראַנט עלעמענט. צוזאמען מיט אים אין יעדער שטעלע, מיר קאָנטראָלירן אויב די קראַנט סומע איז אויך גלאבאלע מאַקסימום אָדער נישט און דערהייַנטיקן די גלאבאלע מאַקסימום לויט דעם.

אַלגערידאַם:

  • שאַפֿן אַ בייַטעוודיק צו קראָם גלאבאלע מאַקסימום. ערשט מיט דעם נעגאַטיוו נומער (INT_MIN).
  • שאַפֿן אַ בייַטעוודיק צו קראָם קראַנט סומע. ערשט מיט נול.
  • לויפן אַ שלייף פון לינקס צו רעכט איבער די מענגע. אויב די קראַנט סומע איז נעגאַטיוו, דערהייַנטיקן עס מיט ווערט 0.
  • לייג דעם קראַנט עלעמענט צו קראַנט סומע און דערהייַנטיקן די גלאבאלע מאַקסימום אויב די קראַנט סומע איז גרעסער ווי גלאבאלע מאַקסימום.
  • ווייַזן די גלאבאלע מאַקסימום.

ימפּלאַמענטיישאַן פֿאַר מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר מאַקסימום סובאַררייַ לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N): זינט עס איז איין פאָרן אַלגערידאַם איבער די מענגע.

זע אויך
דריי קאָנסעקוטיווע שאַנסן לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי 

אָ (1): קיין עקסטרע זכּרון איז געניצט.

1