Максимально можлива різниця двох підмножин масиву


Рівень складності Жорсткий
Часто запитують у Atlassian Каденс Індія Directi FreeCharge працювати PayU Snapchat Times Інтернет Xome
масив Мішанина Сортування

Припустимо, у нас є ціле масив. Постановка задачі “Максимально можлива різниця двох підмножин масиву” вимагає з’ясувати максимально можливу різницю між двома підмножинами масиву.

Умови, яких слід дотримуватися:

  • Масив може містити повторювані елементи, але найвища частота елемента не повинна бути більше 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, нам потрібно повернути різницю обох сум, і це буде нашою відповіддю.

код

Код С ++ для пошуку максимально можливої ​​різниці двох підмножин масиву

#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

Аналіз складності

Складність часу

О (п) де "N" - кількість елементів у масиві. Оскільки ми використовували HashMap, ми можемо виконувати вставку / видалення / пошук в O (1).

Складність простору

О (п) де "N" - кількість елементів у масиві.