סכום תת-רציף הגדול ביותר


רמת קושי קַל
נשאל לעתים קרובות מעבדות חדשנות 24 * 7 נאמן אמזון בעברית דה שו סט עובדות Flipkart טיול Housing.com MakeMyTrip MetLife מיקרוסופט מורגן סטנלי מוניות אולה אורקל חדרי OYO PayU סמסונג Snapdeal Teradata וִיזָה VMware מעבדות וולמארט Zoho
מערך תכנות דינמי

הצהרת בעיה

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

דוגמה

arr[] = {1, -3, 4, -2, 5, -6, 2}
[2, 4]

הסבר: מערך המשנה שמתחיל מאינדקס 2 לאינדקס 4 כולל את הסכום הגדול ביותר של 7 בתוך המערך. כל מערך משנה אחר ייתן סכום קטן מ- 7.

סכום תת-רציף הגדול ביותר

 

arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}
[2, 6]

הסבר: מערך המשנה שמתחיל מאינדקס 2 לאינדקס 6 כולל את הסכום הגדול ביותר של 10 בתוך המערך.

 

אלגוריתם לבעיה הגדולה ביותר של תת-מערך רציף בסכום

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

הסבר

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

הגדר כמה ערכים, כמו ערך מקסימלי לערך המינימלי שמספר שלם יכול להחזיק, maxPoint עד 0, ו התחלה, סוף, ו s עד 0. התחל לחצות את המערך לאורך n. הוסף את אלמנט המערך הנוכחי לסכום maxPoint. אחסן אותו ב- maxPoint, בכל פעם של i תוספות בלולאה, אנו מבצעים פעולה זו. תיקנו כבר את הערך של ערך מקסימלי לערך המינימלי של מספר שלם ובדוק אם maxValue קטן מ- maxPoint. אם זה נכון, אנו הולכים לעדכן את הערך של maxValue מ- maxPoint, התחל ל- s. משתנה התחלה זה יגדיר את הערך של טווח ההתחלה של מערך המשנה הרציף ויש לנו סוף, אותו אנו מעדכנים ב- i (משתנה לולאה).

נבדוק עכשיו אם maxPoint הוא פחות מ- 0, פירושו שתוספת ערכי המערך עד כה היא שלילית. ואז אנו מעדכנים שוב את הערך של maxPoint ל- 0 ו- s ל- i + 1. זֶה s יעזור לנו שוב בהגדרת הערך של טווח ההתחלה ויעזור לנו לגלות את מערך המשנה הגדול ביותר. MaxPoint זה אתחול לאפס מכיוון שעלינו לגלות את הסכום הגדול ביותר ואז אנו הולכים להדפיס את ערך ההתחלה והסיום כאינדיקציה התחלה וסיום של מערך המשנה הגדול ביותר. אם נשתמש בגישה זו נוכל למצוא את הסכום הגדול ביותר של מערך המשנה הצמוד במעבר יחיד.

 

קוד לבעיה הגדולה ביותר של תת-מערך צמוד

קוד C ++

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

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maxPoint += arr[i];

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7

 

קוד Java

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

        for (int i=0; i< size; i++ )
        {
            maxPoint += arr[i];

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}
Sub-Array starting from 2 to 4 has a largest sum of 7

ניתוח מורכבות

מורכבות זמן

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

מורכבות בחלל

השתמשנו במערך קלט 1D יחיד לאחסון המספרים השלמים. ובכך תורם מורכבות שטח ליניארית לבעיה הגדולה ביותר של תת-מערך רציף. O (n) איפה "N" הוא מספר האלמנטים במערך.