Рубрики

Найти максимальное произведение точек двух массивов с вставкой нулей

Даны два массива натуральных чисел размером m и n, где m> n. Нам нужно максимизировать скалярное произведение, вставляя нули во второй массив, но мы не можем нарушать порядок элементов.

Примеры:

Input : A[] = {2, 3 , 1, 7, 8} 
        B[] = {3, 6, 7}        
Output : 107
Explanation : We get maximum dot product after
inserting 0 at first and third positions in 
second array.
Maximum Dot Product : = A[i] * B[j] 
2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 107

Input : A[] = {1, 2, 3, 6, 1, 4}
        B[] = {4, 5, 1}
Output : 46

Спросил в: Directi Интервью

Другой способ взглянуть на эту проблему заключается в том, что для каждой пары элементов element A [i] и B [j], где j> = i, у нас есть два варианта:

  1. Умножаем A [i] и B [j] и добавляем к произведению (включаем A [i]).
  2. Мы исключаем A [i] из продукта (другими словами, мы вставляем 0 в текущую позицию в B [])

Идея состоит в том, чтобы использовать динамическое программирование .

1) Given Array A[] of size 'm' and B[] of size 'n'

2) Create 2D matrix 'DP[n + 1][m + 1]' initialize it
with '0'

3) Run loop outer loop for i = 1 to n
     Inner loop j = i to m

       // Two cases arise
       // 1) Include A[j]
       // 2) Exclude A[j] (insert 0 in B[])      
       dp[i][j]  = max(dp[i-1][j-1] + A[j-1] * B[i -1],
                       dp[i][j-1]) 
      
    // Last return maximum dot product that is 
    return dp[n][m]

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

C ++

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

using namespace std;

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

long long int MaxDotProduct(int A[], int B[],

                            int m, int n)

{

    // Создать 2D матрицу, в которой хранится точечный продукт

    // dp [i + 1] [j + 1] сохраняет товар с учетом B [0..i]

    // и A [0 ... j]. Обратите внимание, что, так как все m> n, мы заполняем

    // значения в верхней диагонали dp [] []

    long long int dp[n+1][m+1];

    memset(dp, 0, sizeof(dp));

  

    // Пройти через все элементы B []

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

  

        // Рассмотрим все значения A [] с индексами больше

        // чем или равный i и вычисляем dp [i] [j]

        for (int j=i; j<=m; j++)

  

            // Два случая возникают

            // 1) Включить A [j]

            // 2) Исключить A [j] (вставить 0 в B [])

            dp[i][j] = max((dp[i-1][j-1] + (A[j-1]*B[i-1])) ,

                            dp[i][j-1]);

  

    // вернуть продукт с максимальной точкой

    return dp[n][m] ;

}

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

int main()

{

    int A[] = { 2, 3 , 1, 7, 8 } ;

    int B[] = { 3, 6, 7 } ;

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

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

    cout << MaxDotProduct(A, B, m, n);

    return 0;

}

Джава

// Java программа для поиска максимума
// скалярное произведение двух массивов

import java.util.*;

  

class GFG 

{
// Функция для вычисления максимума
// Dot Product и возвращаем его

static int MaxDotProduct(int A[], int B[], int m, int n)

{

    // Создать 2D матрицу, в которой хранится точечный продукт

    // dp [i + 1] [j + 1] сохраняет товар с учетом B [0..i]

    // и A [0 ... j]. Обратите внимание, что, так как все m> n, мы заполняем

    // значения в верхней диагонали dp [] []

    int dp[][] = new int[n + 1][m + 1];

    for (int[] row : dp)

    Arrays.fill(row, 0);

  

    // Пройти через все элементы B []

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

  

    // Рассмотрим все значения A [] с индексами больше

    // чем или равный i и вычисляем dp [i] [j]

    for (int j = i; j <= m; j++)

  

        // Два случая возникают

        // 1) Включить A [j]

        // 2) Исключить A [j] (вставить 0 в B [])

        dp[i][j] =

            Math.max((dp[i - 1][j - 1] + 

                    (A[j - 1] * B[i - 1])), dp[i][j - 1]);

  

    // вернуть продукт с максимальной точкой

    return dp[n][m];

}

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

public static void main(String[] args) {

    int A[] = {2, 3, 1, 7, 8};

    int B[] = {3, 6, 7};

    int m = A.length;

    int n = B.length;

    System.out.print(MaxDotProduct(A, B, m, n));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python 3 программа для поиска максимальной точки
# произведение двух массивов

  
# Функция вычисления максимальной точки продукта
# и вернуть

def MaxDotProduct(A, B, m, n):

      

    # Создать 2D матрицу, которая хранит точечный продукт

    # dp [i + 1] [j + 1] хранит товар с учетом

    # B [0..i] и A [0 ... j]. Обратите внимание, что с

    # все m> n, мы заполняем значения в верхнем

    # диагональ дп [] []

    dp = [[0 for i in range(m + 1)] 

             for j in range(n + 1)]

  

    # Пройдите через все элементы B []

    for i in range(1, n + 1, 1):

          

        # Рассмотрим все значения A [] с индексами

        # больше или равно i и вычислить

        # dp [i] [j]

        for j in range(i, m + 1, 1):

              

            # Два случая возникают

            # 1) Включить A [j]

            # 2) Исключить A [j] (вставить 0 в B [])

            dp[i][j] = max((dp[i - 1][j - 1] + 

                            (A[j - 1] * B[i - 1])) , 

                            dp[i][j - 1])

  

    # return Максимальная точка продукта

    return dp[n][m] 

  
Код водителя

if __name__ == '__main__':

    A = [2, 3 , 1, 7, 8]

    B = [3, 6, 7]

    m = len(A)

    n = len(B)

    print(MaxDotProduct(A, B, m, n))

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

C #

// C # программа для поиска максимума
// скалярное произведение двух массивов

using System; 

  

public class GFG{

  

    // Функция для вычисления максимума

    // Dot Product и возвращаем его

    static int MaxDotProduct(int []A, int []B, int m, int n)

    {

        // Создать 2D матрицу, в которой хранится точечный продукт

        // dp [i + 1] [j + 1] сохраняет товар с учетом B [0..i]

        // и A [0 ... j]. Обратите внимание, что, так как все m> n, мы заполняем

        // значения в верхней диагонали dp [] []

        int [,]dp = new int[n + 1,m + 1];

  

        // Пройти через все элементы B []

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

  

        // Рассмотрим все значения A [] с индексами больше

        // чем или равный i и вычисляем dp [i] [j]

        for (int j = i; j <= m; j++)

  

            // Два случая возникают

            // 1) Включить A [j]

            // 2) Исключить A [j] (вставить 0 в B [])

            dp[i,j] =

                Math.Max((dp[i - 1,j - 1] + 

                        (A[j - 1] * B[i - 1])), dp[i,j - 1]);

  

        // вернуть продукт с максимальной точкой

        return dp[n,m];

    }

  

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

    public static void Main() {

        int []A = {2, 3, 1, 7, 8};

        int []B = {3, 6, 7};

        int m = A.Length;

        int n = B.Length;

        Console.Write(MaxDotProduct(A, B, m, n));

    }

}

  
/ * Этот код предоставлен 29AjayKumar * /


Выход:

107

Сложность времени: O (нм)

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

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

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

Найти максимальное произведение точек двух массивов с вставкой нулей

0.00 (0%) 0 votes