פתרון מקסימלי למפתח תת-מערך


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג Byte סיסקו פייסבוק גולדמן זאקס Google פי מורגן לינקדין מיקרוסופט אורקל פייפאל Paytm סופר
מערך הפרד ומשול תכנות דינמי

הצהרת בעיה

בהינתן מערך שלם מספרים, מצא את הצמוד מערך משנה (המכיל מספר אחד לפחות) בעל הסכום הגדול ביותר ומחזיר את סכומו.

דוגמה

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

הסבר:

[4, -1,2,1] יש את הסכום הגדול ביותר = 6.

nums = [-1]
-1

גישה 1 (לחלק ולכבוש)

בגישה זו נדון על טכניקות חלוקה וכיבוש לפתרון בעיה זו. אנו מנסים למצוא את אותו מערך משנה צמוד שיש בו סכום מקסימלי. אז אנו יכולים לומר כי מערך המשנה האופטימלי עשוי להיות בכל חלק במערך. אז אנו מקבלים שלושה מקרים שיכסו את כל האפשרויות:

1 מקרה:
מערך המשנה המקסימלי טמון לחלוטין במחצית השמאלית של המערך.
2 מקרה:
מערך תת מקסימום נמצא לגמרי במחצית הימנית של המערך.
3 מקרה:
חלק חלקי מערך המשנה המקסימלי נמצא במחצית השמאלית וחלק חלקי נוסף ממנו נמצא במחצית השנייה (כלומר, תת-המערך חוצה את האלמנט האמצעי של המערך)

כפי שאנו יכולים לראות מקרה 1 ומקרה 2 הוא בעצם תת-בעיה של מערך בגודל N / 2 בעל הגדרה זהה לבעיה העיקרית. כאשר N הוא גודל המערך הנוכחי. אז אנחנו יכולים פשוט חוזר על עצמו הפונקציה מעל שני חצאי המערך.
כעת החלק העיקרי הוא מקרה 3 שעלינו לפתור בפונקציה הנוכחית ואז נוכל להחזיר את הסכום המרבי מבין 3 המקרים הללו.

בואו נראה כיצד נוכל לפתור מקרה 3:

נניח שיש לנו מערך = [-2,1, -3,4, -1,2,1, -5,4]
אנו מוצאים אינדקס אמצעי לחלק אותו לשני חצאים שווים.
מדד אמצע = (0 + 9) / 2 = 4

פתרון מקסימלי למפתח תת-מערך

כמו שבמקרה 3 נאמר שסכום מקסימלי יחצה את האלמנט האמצעי. אז ננסה למצוא את הסכום המקסימלי החל מאמצע וכלה בצד שמאל. באופן דומה נמצא את הסכום המקסימלי החל מ- (mid + 1) וכלה בצד ימין. בדרך זו נמצא את מערך המשנה המקסימלי החוצה את הגבול האמצעי למקרה 3.

אַלגוֹרִיתְם:

  • חלקו את המערך לשני חצאים.
  • מצא באופן רקורסיבי את הסכום המקסימלי למערך משנה עבור מערך משנה שמאלי.
  • מצא באופן רקורסיבי את הסכום המקסימלי למערך משנה למערך משנה נכון.
  • מצא את הסכום המרבי של תת-המערך החוצה את נקודת האמצע.
  • החזר את המקסימום של מעל שלושה סכומים.

יישום לפתרון Leetcode מקסימלי של תת-מערך

תוכנית 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

ניתוח מורכבות לפתרון מקסימלי של Leetcode במערך המשנה

מורכבות זמן

O (NlogN): בחלוקה ובכיבוש למעשה אנו מחלקים את הבעיה לשני חצאים שווים בגודל N / 2. שוב זה מתחלק בגודל N / 4 וכן הלאה. מכאן שהרמה העמוקה ביותר של רקורסיה תהיה logN כאשר גודל המערך יהיה 1 ואנחנו חוזרים משם. בכל רמה שאנחנו מבצעים O (n) משימה ולכן מורכבות הזמן הכוללת תהיה O (NlogN). הנה יחס ההישנות

מורכבות בחלל 

O (logN): שטח logN משמש לערימת רקורסיה.

 

גישה 2 (שיטת קדאנה)

השיטה של ​​Kadane היא אלגוריתם מפורסם עבור סכום תת מערך. בשיטה זו אנו פשוט חוזרים פעם אחת על מערך הקלט הנתון. אנו לוקחים סכום נוכחי בהתחלה עם ערך אפס ומוסיפים כל אלמנט בנתיב. אנו מוסיפים כל אלמנט לסכום הנוכחי אם הסכום הנוכחי הקודם אינו שלילי או אחרת אנו פשוט שוברים את ההמשכיות ומעדכנים את הסכום הנוכחי באלמנט הנוכחי. יחד עם זה בכל עמדה אנו בודקים אם הסכום הנוכחי הוא גם מקסימום גלובלי או לא ומעדכנים את המקסימום הגלובלי לפיו.

אַלגוֹרִיתְם:

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

יישום לפתרון Leetcode מקסימלי של תת-מערך

תוכנית 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

ניתוח מורכבות לפתרון מקסימלי של Leetcode במערך המשנה

מורכבות זמן

O (N): מכיוון שמדובר באלגוריתם אחד לעבור על המערך.

מורכבות בחלל 

O (1): לא משתמשים בזיכרון נוסף.