Максимално възможна разлика от две подмножества на масив


Ниво на трудност Трудно
Често задавани в Atlassian Каденс Индия Directi FreeCharge опера PayU Snapchat Times Internet Xome
Array Хашиш сортиране

Да предположим, че имаме цяло число масив. Изявлението за проблема „Максимално възможна разлика на две подмножества от масив“ иска да открие максимално възможната разлика между двете подмножества на масив.

Условия, които трябва да се спазват:

  • Масивът може да съдържа повтарящи се елементи, но най-високата честота на даден елемент не трябва да бъде по-голяма от 2.
  • Трябва да направите две подмножества, така че разликата между сумата на съответните им елементи да е максимална.
  • Всички елементи на масива трябва да бъдат разделени между двете подмножества, без да оставяте никакъв елемент зад себе си.
  • Два елемента не трябва да бъдат еднакви в рамките на подмножество.

Пример

Максимално възможна разлика от две подмножества на масив

arr[] = {2, 5, -3, -1, 5, 7}
13

Обяснение

Подмножество → (2, 7, 5) - (-3, -1, 5) = 13

{1, 5, 3, -1, -5, 6}
21

Обяснение

Подмножество → (1, 3, 5, 6) - (-5, -1) = 21

алгоритъм

  1. Декларирайте две Карти, един за положителен и един за отрицателен елемент.
  2. Съхранявайте положителните елементи и броя им в една карта.
  3. Продължавайте да събирате всички положителни елементи с честота 1 и да ги съхранявате подмножество1.
  4. Съхранявайте отрицателния елемент и броя му в друга карта.
  5. Продължавайте да събирате всички отрицателни елементи с честота 1 и да ги съхранявате в подмножество2.
  6. Връщане на подмножество1-подмножество2.

Обяснение

Дадохме масив, трябва да открием разликата между сумата на елементите на две подмножества и тази трябва да бъде максимална. Ще използваме a Карта. хеширане осигурява ефективен начин за решаване на този въпрос. Ще използваме две Карти. Едната е за готови операции върху положителни елементи, а друга за отрицателни елементи. Масивът може да съдържа както положителни, така и отрицателни елементи, така че трябва да се справим и с това нещо.

Ще вземем масив и карта. Ще изберем всеки елемент от масива и ще проверим дали е по-голям от 0. Тогава ще го съхраним в картата с броя на неговите повторения. След съхраняване на честотите на положителните елементи ще съберем всички стойности на масив, които са по-големи от 0 и също имат честота само 1, означава, че трябва да игнорираме тези елементи, които идват няколко пъти или повече от веднъж.

Същото нещо ще се направи с отрицателни елементи, ще изберем всеки елемент от масив и този път ще проверим дали е по-малко от 0. Ще го съхраним в картата (превръщайки го в положително число) с неговия брой на прояви. След съхраняване на честотите на отрицателните елементи ще съберем всички стойности на масив, които са по-малки от 0, а също и с честота само 1. Тук също трябва да игнорираме тези елементи, които идват няколко пъти или повече от веднъж.

След получаване на сумата от всички положителни и отрицателни елементи последва условието, че елементите имат само честота 1, трябва да върнем разликата и на двете суми и това ще бъде нашият отговор.

код

C ++ код за намиране на максимално възможната разлика на две подмножества от масив

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

Java код за намиране на максимално възможната разлика от две подмножества на масив

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

Анализ на сложността

Сложност във времето

О (п) където "н" е броят на елементите в масива. Тъй като използвахме HashMap, можем да извършим вмъкване / изтриване / търсене в O (1).

Сложност на пространството

О (п) където "н" е броят на елементите в масива.