Фарқияти максималии ду зермаҷмӯи массив


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Atlassian Cadence Ҳиндустон Directi FreeCharge Опера PayU Snapchat Интернет Times Xome
тартиботи ҳарбӣ Хаш Sorting

Фарз мекунем, ки мо дорем ҳамаҷониба асал. Изҳороти проблемавии "Фарқияти максималии имконпазири ду зершаби массив" дархост мекунад, ки фарқи максималии имконпазирро байни ду зергурӯҳи массив муайян кунанд.

Шартҳои риояшаванда:

  • Массив метавонад унсурҳои такрориро дар бар гирад, аммо басомади баландтарини элемент набояд аз 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. Бозгаштан 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) дохилкунӣ / несткунӣ / ҷустуҷӯро иҷро кунем.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.