מערך משנה מקסימלי של מוצרים


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית סיסקו מיקרוסופט מורגן סטנלי מינטרה PayU פעמים באינטרנט Zoho
מערך

הצהרת בעיה

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

דוגמה

arr[] = { 2, -2, 3, 5}
15

הסבר

האלמנטים במערך המשנה הם 3 ו -5 המחזיקים את התוצר המרבי של כל מערכי המשנה האפשריים.

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

1. Traverse the array from i = 0 to less than the value n(length of the given array).
  1. Check if arr[i] is greater than 0, if true
    1. Find out the maximumRange by multiplying each value of an array to itself.
    2. Find out the minimumRange between the product of minimumRange and arr[i] and 1.
    3. Mark flag is equal to 1.
  2. If the value of the array is equal to 0, then mark the minimum and maximum range to 1.
  3. Else find out the maximum between the product of minimumRange and arr[i] and 1 and find out the minimumRange by the product value of maximumRange and arr[i].
  4. If maxValue is less than the value of the maximumRange then store the value of maximumRange to maxValue.’
2. Check if the flag is equal to 0 and also maxValue is equal to 1, then return 0
3. Return maxValue.

הסבר

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

עכשיו, עלינו רק להתמקד במוצר המקסימלי שניתן לייצר עם כל מערכי המשנה האפשריים. תהיה לנו עין על ה- MaximumRange וה- MinimumRange. ב- maxValue, אנו הולכים לאחסן כאן את המוצר המקסימלי. הדגל הוא המשתנה כדי לבדוק אם מצאנו מספר חיובי כלשהו וגם המוצר המרבי שאינו 1 קיים.

אנו נעבור את המערך בין 0 ל- n (כאשר n הוא אורך המערך). נבדוק אם arr [i] גדול מ- 0. אם זה נכון, נא לאחסן את המוצר של maximumRange ו- arr [i] ל- MaximumRange. ואז בררו את הערך המינימלי בין המוצר של minimumRange ו- arr [i] ו- 1, ואחסנו אותו ל- MinimumRange.

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

אם אף אחד מהתנאים לא מתקיים. ואז בררו את הערך המקסימלי בין המוצר של minimumRange לבין ה- arr [i] ואחסנו אותו ל- MaximumRange. המוצר של ה- MaximumRange וה- arr [i] יאוחסן ל- MinimumRange. בכל מעבר, עלינו להשוות לערך הגדול יותר ולעדכן אותו ב- maxValue ולבסוף להחזיר את maxValue שיחזיק את המוצר המקסימלי של כל מערכי המשנה האפשריים.

מערך משנה מקסימלי של מוצרים

קופונים

קוד CPP כדי למצוא מערך משנה מקסימלי של מוצרים

#include<iostream>

using namespace std;

int maxSubarrayProduct(int arr[], int n)
{
    int maximumRange = 1;
    int minimumRange = 1;

    int maxValue = 1;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            maximumRange = maximumRange * arr[i];
            minimumRange = min(minimumRange * arr[i], 1);
            flag = 1;
        }
        else if (arr[i] == 0)
        {
            maximumRange = 1;
            minimumRange = 1;
        }
        else
        {
            int temp = maximumRange;
            maximumRange = max(minimumRange * arr[i], 1);
            minimumRange = temp * arr[i];
        }
        if (maxValue < maximumRange)
            maxValue = maximumRange;
    }
    if (flag == 0 && maxValue == 1)
        return 0;
    return maxValue;
}
int main()
{
    int arr[] = { 2,-2,-3,-5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "<< maxSubarrayProduct(arr, n);
    return 0;
}
Maximum Sub array product is 15

קוד Java כדי למצוא מערך מוצר מקסימלי

class productSubarray
{
    public static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        int maximumRange = 1;
        int minimumRange = 1;

        int maxValue = 1;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)
            {
                maximumRange = maximumRange * arr[i];
                minimumRange = Math.min(minimumRange * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0)
            {
                maximumRange = 1;
                minimumRange = 1;
            }
            else
            {
                int temp = maximumRange;
                maximumRange = Math.max(minimumRange * arr[i], 1);
                minimumRange = temp * arr[i];
            }
            if (maxValue < maximumRange)
                maxValue = maximumRange;
        }
        if (flag == 0 && maxValue == 1)
            return 0;
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,-2,-3,-5};
        System.out.println("Maximum Sub array product is "+ maxSubarrayProduct(arr));
    }
}
Maximum Sub array product is 15

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

מורכבות זמן

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

מורכבות בחלל

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