Массивті шешім кодындағы екі элементтің максималды өнімі


Күрделілік дәрежесі оңай
Жиі кіреді Samsung
Array

«Массивтегі екі элементтің максималды өнімі» мәселесінде біздің мақсатымыз екі индексті табу i және j берілген бүтін сандар жиымында a, өнім (a [i] - 1) * (a [j] - 1) максималды болатындай. Массивтің кем дегенде 2 элементі бар және барлық элементтері оң. Қажетті өнім бүтін диапазонға сәйкес келетін мәселе. Оңтайлы болу үшін (a [i] - 1) * (a [j] - 1) мәнін басып шығаруымыз керек i & j.

мысал

a = {1 , 4 , 5 , 3 , 6 , 4}
2

Түсіндіру

6 және 5 ең үлкен және екінші үлкен сандар екені анық. Сонымен, өнім = (a [i] - 1) * (a [j] - 1) = 20.

Тәсіл (сұрыптау)

Өнім: (a [i] - 1) * (a [j] - 1) a [i] және a [j] массивтің ең үлкен екі элементі болғанда максималды болады. Екі ең үлкен элементтерден тұратын i және j индекстерін табудың орнына біз аламыз сорт The массив өсу ретімен. Бұл ең үлкен екі элементтің соңында екендігіне көз жеткізеді. Демек, өнім (a [n - 1] - 1) * (a [n - 2] - 1) қажетті нәтиже болады.

Алгоритм

  1. Массивті сұрыптау
  2. Нәтижені басып шығарыңыз: (a [n - 1] - 1) * (a [n - 2] - 1)

Массивтегі екі элементтің максималды өнімін табу алгоритмін жүзеге асыру

C ++ бағдарламасы

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

int maxProduct(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());
    return ((a[n - 1] - 1) * (a[n - 2] - 1));
}


int main()
{
    vector <int> a = {1 , 4 , 5 , 3 , 6 , 4};
    cout << maxProduct(a) << '\n';
}

Java бағдарламасы

import java.util.Arrays;

class maximum_product
{
    public static void main(String args[])
    {
        int[] a = {1 , 4 , 5 , 3 , 6 , 4};
        System.out.println(maxProduct(a));
    }

    static int maxProduct(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);
        return (a[n - 1] - 1) * (a[n - 2] - 1);
    }
}
20

Массивтегі екі элементтің максималды өнімін табудың күрделілігін талдау

Уақыттың күрделілігі

O (NlogN), N = массивтің өлшемі. O (NlogN) уақытты алатын массивті сұрыптаймыз.

Ғарыштың күрделілігі

O (1), өйткені біз тұрақты жад кеңістігін қолданамыз.

Тәсіл (оңтайлы)

Жоғарыда қарастырғанымыздай, массивтің ең үлкен екі элементін табу керек. Барлық массивті сұрыптай отырып, біз асыра орындау қажетті жұмыс. Сонымен, массивтен бірінші және екінші үлкен элементті қарапайым салыстыру амалдары арқылы табу оңтайлы. Демек, қажетті нәтижені келесідей алуға болады (firstMax - 1) * (secondMax - 1).

Массивті шешім кодындағы екі элементтің максималды өнімі

Алгоритм

  1. Екі айнымалыны инициализациялаңыз: firstMax және secondMax нөл ретінде (массивтегі кез келген мән оларды іштей жаңартады).
  2. Массивтің басынан аяғына дейін циклды іске қосыңыз.
  3. Әрбір элемент үшін:
    • Оның firstMax-тен үлкен екенін тексеріңіз:
      • Егер рас болса:
        • SecondMax = firstMax орнатыңыз
        • FirstMax = ағымдағы элементті жаңартыңыз
      • Басқа:
        • Егер бұл secondMax-тан үлкен болса
          • SecondMax = ағымдағы элементті жаңартыңыз
  4. Нәтижені басып шығарыңыз

Массивтік шешім кодындағы екі элементтің максималды өнімін табу алгоритмін жүзеге асыру

C ++ бағдарламасы

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

int maxProduct(vector <int> &a)
{
    int firstMax = 0 , secondMax = 0 , n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] > firstMax)
        {
            secondMax = firstMax;
            firstMax = a[i];
        }
        else if(a[i] > secondMax)
            secondMax = a[i];

    return (firstMax - 1) * (secondMax - 1);
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 3 , 6 , 4};
    cout << maxProduct(a) << '\n';
}

Java бағдарламасы

class maximum_product
{
    public static void main(String args[])
    {
        int[] a = {1 , 4 , 5 , 3 , 6 , 4};
        System.out.println(maxProduct(a));
    }

    static int maxProduct(int[] a)
    {
        int firstMax = 0 , secondMax = 0 , n = a.length;
        for(int i = 0 ; i < n ; i++)
            if(a[i] > firstMax)
            {
                secondMax = firstMax;
                firstMax = a[i];
            }
            else if(a[i] > secondMax)
                secondMax = a[i];

        return (firstMax - 1) * (secondMax - 1);
    }
}
20

Массивтік шешім кодындағы екі элементтің максималды өнімін табудың күрделілігі

Уақыттың күрделілігі

O (N), N = Массивтің өлшемі. Қарапайым салыстыру операциялары үшін сызықтық циклды іске қосамыз.

Ғарыштың күрделілігі

O (1), ретінде тұрақты жады қолданылады.