סכום מקסימלי של הגדלת המשך


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית קנאות מיקרוסופט מורגן סטנלי
מערך תכנות דינמי

הצהרת בעיה

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

דוגמה

arr[] = {2,4,5,10,1,12}
33

הסבר: סכום של {2, 4, 5, 10, 12} ⇒ 33. לקחנו את כל מערך הקלט הראשוני למעט האלמנט באינדקס 4 (אינדקס מבוסס 0) כדי לספק את המצב הממוין שלנו. המשך זה נותן לנו את התוצאה הטובה ביותר. כל המשך אחר יביא לסכום הנמוך מהסכום הנוכחי.

arr[] = {3,5,7,1,20,4,12}
35

הסבר: סכום של {3, 5, 7, 20} ⇒ 35. הנה, הסרנו את 1 ו -4 שהופך את שאר המערך למיון. ואז האלמנטים הנותרים מייצרים סכום מקסימלי לאחר מכן.

 

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

1. Declare an array say maxSumIS as the same size as the length of an array.
2. Set the output to 0.
3. Copy each element of an array into the created array.
4. Traverse the array from i=1 to i<n(length of the array)
  Now in another loop, from j=0 to j<i,
    Check if arr[i] is greater than arr[j] and maxSumIS[i] is less than maxSumIS[j]+arr[i]N,
      Then update the value of maxSumIS[i] = maxSumIS[j] + arr[i].
5. Traverse the array, and find out the maximum of all the elements from maxSumIS and return that value.

 

הסבר

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

נחצה את המערך בפעם הראשונה. הפעם הראשונה תהיה העתקת הערך של מערך נתון למערך שיצרנו maxSumIS []. זֶה maxSumIS [] המערך מתעדכן בכל פעם שמצבנו מתקיים. אז נחצה תחילה את המערך מ- i = 1 מכיוון שנשתמש באינדקס הראשון במערך maxSumIS. לכן בדיוק לקחנו את הערך של הלולאה השנייה מ- 0 ל- i. אנחנו הולכים לבדוק את המצב אם arr [i] גדול יותר מה- arr [j], וגם maxSumIS [j] קטן מסכום שני האלמנטים הקודמים על פי המדדים הנוכחיים i ו- j. אם שני התנאים מתקיימים, אנו מעדכנים את הערך של maxSumIS [i] לסכום האלמנט הנוכחי של שני המדדים כ- maxSumIS [j] ו- arr [i].

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

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

סכום מקסימלי של הגדלת המשך

קוד להמשך הגדלת הסכום המרבי

קוד C ++

#include<iostream>
using namespace std;

int getMaximumSumIS(int arr[], int n)
{
    int i, j, output = 0;
    int maxSumIS[n];

    for ( i = 0; i < n; i++ )
        maxSumIS[i] = arr[i];

    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                maxSumIS[i] = maxSumIS[j] + arr[i];

    // Take the maximum out of all the possible answers
    for ( i = 0; i < n; i++ )
        if ( output < maxSumIS[i] )
            output = maxSumIS[i];

    return output;
}
int main()
{
    int arr[] = {2,4,5,10,1,12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total sum of Maximum Sum Increasing Subsequence : " << getMaximumSumIS( arr, n );
    return 0;
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

קוד Java

class MaximumSumIncreasingsubsequence
{
    public static int getMaximumSumIS(int arr[], int n)
    {
        int i, j, output = 0;
        int maxSumIS[] = new int[n];

        for (i = 0; i < n; i++)
            maxSumIS[i] = arr[i];

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                    maxSumIS[i] = maxSumIS[j] + arr[i];

        // Take the maximum out of all the possible answers
        for (i = 0; i < n; i++)
            if (output < maxSumIS[i])
                output = maxSumIS[i];

        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2,4,5,10,1,12};
        int n = arr.length;
        System.out.println("Total sum of Maximum Sum Increasing Subsequence : "+getMaximumSumIS(arr, n));
    }
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

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

מורכבות זמן

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

מורכבות בחלל

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