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


Сложный уровень Жесткий
Часто спрашивают в Atlassian Cadence Индия Directi Свободный заряд Opera PayU Snapchat Таймс Интернет Xome
массив Hash Сортировка

Предположим, у нас есть целое массив. В постановке задачи «Максимально возможная разница двух подмножеств массива» предлагается выяснить максимально возможную разницу между двумя подмножествами массива.

Условия, которые необходимо соблюдать:

  • Массив может содержать повторяющиеся элементы, но максимальная частота элемента не должна быть больше 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 и сохранять их в subset1.
  4. Сохраните отрицательный элемент и его количество на другой карте.
  5. Продолжайте складывать все отрицательные элементы с частотой 1 и сохранять их в subset2.
  6. Вернуть subset1-subset2.

объяснение

Мы дали массив, нам нужно найти разницу между суммой элементов двух подмножеств, которая должна быть максимальной. Мы собираемся использовать Карта. хеширования предоставляет эффективный способ решить этот вопрос. Мы собираемся использовать две карты. Один предназначен для выполненных операций с положительными элементами, а другой - с отрицательными. Массив может содержать как положительные, так и отрицательные элементы, так что мы тоже должны справиться с этим.

Возьмем массив и карту. Мы собираемся выбрать каждый элемент массива и проверить, больше ли он 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).

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.