Рубрики

Максимально возможная сумма окна в массиве, чтобы элементы одного окна в другом массиве были уникальными

Даны два массива A и B одинакового количества элементов. Задача состоит в том, чтобы найти максимально возможную сумму окна в массиве B, чтобы элементы этого окна в A [] были уникальными.

Примеры:

Input : A = [0, 1, 2, 3, 0, 1, 4] 
        B = [9, 8, 1, 2, 3, 4, 5]
Output : sum = 20
The maximum sum possible in B[] such that 
all corresponding elements in A[] are unique 
is (9+8+1+2) = 20.

Input : A = [0, 1, 2, 0, 2]
        B = [5, 6, 7, 8, 2]
Output :sum = 21

Простое решение состоит в том, чтобы рассмотреть все подмассивы B []. Для каждого подмассива проверьте, различны ли элементы одного и того же подмассива в A []. Если он отличается, сравните сумму с результатом и обновите результат.
Временная сложность этого решения составляет O (n 2 )

Эффективным решением является использование хеширования.

  1. Создайте пустую хеш-таблицу.
  2. Элементы массива перемещения. Делайте следующее для каждого элемента A [i].
    • Пока A [i] присутствует в хеш-таблице, продолжайте удалять элементы из начала текущего окна и продолжайте вычитать начальный элемент окна B [] из текущей суммы.
  3. Добавьте B [i] к текущей сумме и обновите результат, если текущая сумма становится больше.
  4. Вернуть результат.

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ программа для поиска максимума
// возможная сумма окна в одном
// массив такой, что элементы в том же
// окно другого массива уникально.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата максимальной суммы окна
// в B [] согласно заданным ограничениям.

int returnMaxSum(int A[], int B[], int n)

{

    // Карта используется для хранения элементов

    // и их количество.

    unordered_set<int> mp;

  

    int result = 0; // Инициализировать результат

  

    // вычисление максимально возможного

    // сумма для каждого подмассива, содержащего

    // уникальные элементы.

    int curr_sum = 0, curr_begin = 0;

    for (int i = 0; i < n; ++i) {

  

        // Удалить все дубликаты

        // экземпляры A [i] в

        // текущее окно.

        while (mp.find(A[i]) != mp.end()) {

            mp.erase(A[curr_begin]);

            curr_sum -= B[curr_begin];

            curr_begin++;

        }

  

        // Добавить текущий экземпляр A [i]

        // для отображения и для текущей суммы.

        mp.insert(A[i]);

        curr_sum += B[i];

  

        // Обновить результат, если текущий

        // сумма больше.

        result = max(result, curr_sum);

    }

  

    return result;

}

  
// Код драйвера

int main()

{

    int A[] = { 0, 1, 2, 3, 0, 1, 4 };

    int B[] = { 9, 8, 1, 2, 3, 4, 5 };

    int n = sizeof(A)/sizeof(A[0]);

    cout << returnMaxSum(A, B, n);

    return 0;

}

Джава

// Java программа для поиска максимума
// возможная сумма окна в одном
// массив такой, что элементы в том же
// окно другого массива уникально.

import java.util.HashSet;

import java.util.Set;

  

public class MaxPossibleSuminWindow

{

    // Функция для возврата максимальной суммы окна

    // в A [] согласно заданным ограничениям.

    static int returnMaxSum(int A[], int B[], int n)

    {

  

        // Карта используется для хранения элементов

        // и их количество.

        Set<Integer> mp = new HashSet<Integer>();

  

        int result = 0; // Инициализировать результат

  

        // вычисление максимально возможного

        // сумма для каждого подмассива, содержащего

        // уникальные элементы.

        int curr_sum = 0, curr_begin = 0;

        for (int i = 0; i < n; ++i)

        {

            // Удалить все дубликаты

            // экземпляры A [i] в

            // текущее окно.

            while (mp.contains(A[i]))

            {

                mp.remove(A[curr_begin]);

                curr_sum -= B[curr_begin];

                curr_begin++;

            }

  

            // Добавить текущий экземпляр A [i]

            // для отображения и для текущей суммы.

            mp.add(A[i]);

            curr_sum += B[i];

  

            // Обновить результат, если текущий

            // сумма больше.

            result = Integer.max(result, curr_sum);

  

        }

        return result;

    }

  

    // Код драйвера для проверки вышеуказанного метода

    public static void main(String[] args)

    {

        int A[] = { 0, 1, 2, 3, 0, 1, 4 };

        int B[] = { 9, 8, 1, 2, 3, 4, 5 };

        int n = A.length;

        System.out.println(returnMaxSum(A, B, n));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Python3 программа для поиска максимума
# возможная сумма окна в одном
# массив такой, что элементы в том же
# Окно другого массива уникально.

  
# Функция для возврата максимальной суммы окна
# в B [] в соответствии с заданными ограничениями.

def returnMaxSum(A, B, n): 

   

    # Карта используется для хранения элементов

    # и их количество.

    mp = set()

    result = 0 # Инициализировать результат

  

    # расчет максимально возможного

    # сумма для каждого подмассива, содержащего

    # уникальные элементы.

    curr_sum = curr_begin = 0 

    for i in range(0, n):  

  

        # Удалить все повторяющиеся экземпляры

        # A [i] в текущем окне.

        while A[i] in mp:  

            mp.remove(A[curr_begin]) 

            curr_sum -= B[curr_begin] 

            curr_begin += 1

           

        # Добавить текущий экземпляр A [i]

        # к карте и к текущей сумме.

        mp.add(A[i]) 

        curr_sum += B[i] 

  

        # Обновить результат, если текущий

        # сумма больше

        result = max(result, curr_sum) 

       

    return result 

  
# Код драйвера

if __name__ == "__main__":

   

    A = [0, 1, 2, 3, 0, 1, 4]  

    B = [9, 8, 1, 2, 3, 4, 5

    n = len(A) 

    print(returnMaxSum(A, B, n))

  
# Этот код предоставлен Rituraj Jain

C #

// C # программа для поиска максимума
// возможная сумма окна в одном
// массив такой, что элементы в том же
// окно другого массива уникально.

using System;

using System.Collections.Generic;

  

public class MaxPossibleSuminWindow

{

      

    // Функция для возврата максимальной суммы окна

    // в A [] согласно заданным ограничениям.

    static int returnMaxSum(int []A, int []B, int n)

    {

  

        // Карта используется для хранения элементов

        // и их количество.

        HashSet<int> mp = new HashSet<int>();

  

        int result = 0; // Инициализировать результат

  

        // вычисление максимально возможного

        // сумма для каждого подмассива, содержащего

        // уникальные элементы.

        int curr_sum = 0, curr_begin = 0;

        for (int i = 0; i < n; ++i)

        {

            // Удалить все дубликаты

            // экземпляры A [i] в

            // текущее окно.

            while (mp.Contains(A[i]))

            {

                mp.Remove(A[curr_begin]);

                curr_sum -= B[curr_begin];

                curr_begin++;

            }

  

            // Добавить текущий экземпляр A [i]

            // для отображения и для текущей суммы.

            mp.Add(A[i]);

            curr_sum += B[i];

  

            // Обновить результат, если текущий

            // сумма больше.

            result = Math.Max(result, curr_sum);

  

        }

        return result;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int []A = { 0, 1, 2, 3, 0, 1, 4 };

        int []B = { 9, 8, 1, 2, 3, 4, 5 };

        int n = A.Length;

        Console.WriteLine(returnMaxSum(A, B, n));

    }

  
/ * Этот код был добавлен
от PrinciRaj1992 * /


Выход:

 20

Временная сложность этого решения составляет O (n). Обратите внимание, что каждый элемент массива вставляется и удаляется не более одного раза из массива.

Эта статья предоставлена Parth Trehan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Максимально возможная сумма окна в массиве, чтобы элементы одного окна в другом массиве были уникальными

0.00 (0%) 0 votes