Рубрики

Найти конкретную пару в матрице

Учитывая nxn матрицу mat [n] [n] целых чисел, найдите максимальное значение mat (c, d) — mat (a, b) для всех вариантов выбора индексов, так что c> a и d> b.

Пример:

Input:
mat[N][N] = {{ 1, 2, -1, -4, -20 },
             { -8, -3, 4, 2, 1 }, 
             { 3, 8, 6, 1, 3 },
             { -4, -1, 1, 7, -6 },
             { 0, -4, 10, -5, 1 }};
Output: 18
The maximum value is 18 as mat[4][2] 
- mat[1][0] = 18 has maximum difference. 

Программа должна делать только ОДИН обход матрицы. т.е. ожидаемая сложность по времени составляет O (n 2 )

Простым решением было бы применить Brute-Force. Для всех значений mat (a, b) в матрице мы находим mat (c, d), который имеет максимальное значение, такое что c> a и d> b, и продолжает обновлять максимальное найденное значение. Наконец мы возвращаем максимальное значение.

Ниже приведена его реализация.

C ++

// Наивный метод, чтобы найти максимальное значение mat [d] [e]
// - ma [a] [b] такой, что d> a и e> b
#include <bits/stdc++.h>

using namespace std;

#define N 5

  
// Функция возвращает максимальное значение A (d, e) - A (a, b)
// по всем вариантам индексов, так что оба d> a
// и e> b.

int findMaxValue(int mat[][N])

{

    // сохраняет максимальное значение

    int maxValue = INT_MIN;

  

    // Рассмотрим все возможные пары mat [a] [b] и

    // mat [d] [e]

    for (int a = 0; a < N - 1; a++)

    for (int b = 0; b < N - 1; b++)

        for (int d = a + 1; d < N; d++)

        for (int e = b + 1; e < N; e++)

            if (maxValue < (mat[d][e] - mat[a][b]))

                maxValue = mat[d][e] - mat[a][b];

  

    return maxValue;

}

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

int main()

{

int mat[N][N] = {

                { 1, 2, -1, -4, -20 },

                { -8, -3, 4, 2, 1 },

                { 3, 8, 6, 1, 3 },

                { -4, -1, 1, 7, -6 },

                { 0, -4, 10, -5, 1 }

            };

    cout << "Maximum Value is "

        << findMaxValue(mat);

  

    return 0;

}

Джава

// Наивный метод, чтобы найти максимальное значение mat1 [d] [e]
// - ma [a] [b] такой, что d> a и e> b

import java.io.*;

import java.util.*;

   

class GFG 

{

    // Функция возвращает максимальное значение A (d, e) - A (a, b)

    // по всем вариантам индексов, так что оба d> a

    // и e> b.

    static int findMaxValue(int N,int mat[][])

    {

        // сохраняет максимальное значение

        int maxValue = Integer.MIN_VALUE;

       

        // Рассмотрим все возможные пары mat [a] [b] и

        // mat1 [d] [e]

        for (int a = 0; a < N - 1; a++)

          for (int b = 0; b < N - 1; b++)

             for (int d = a + 1; d < N; d++)

               for (int e = b + 1; e < N; e++)

                  if (maxValue < (mat[d][e] - mat[a][b]))

                      maxValue = mat[d][e] - mat[a][b];

       

        return maxValue;

    }

       

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

    public static void main (String[] args) 

    {

        int N = 5;

  

        int mat[][] = {

                      { 1, 2, -1, -4, -20 },

                      { -8, -3, 4, 2, 1 },

                      { 3, 8, 6, 1, 3 },

                      { -4, -1, 1, 7, -6 },

                      { 0, -4, 10, -5, 1 }

                   };

  

        System.out.print("Maximum Value is "

                         findMaxValue(N,mat));

    }

}

   
// Этот код добавлен
// Пракрити Гупта

Python 3

# Наивный способ найти максимум
# значение mat [d] [e] - mat [a] [b]
# такое, что d> a и e> b

N = 5

  
# Функция возвращает максимум
# значение A (d, e) - A (a, b) более
# все варианты индексов такие
# что и d> a, и e> b.

def findMaxValue(mat):

      

    # хранит максимальное значение

    maxValue = 0

  

    # Рассмотрим все возможные пары

    # mat [a] [b] и mat [d] [e]

    for a in range(N - 1):

        for b in range(N - 1):

            for d in range(a + 1, N):

                for e in range(b + 1, N):

                    if maxValue < int (mat[d][e] - 

                                       mat[a][b]):

                        maxValue = int(mat[d][e] - 

                                       mat[a][b]);

  

    return maxValue;

  
Код водителя

mat = [[ 1, 2, -1, -4, -20 ],

       [ -8, -3, 4, 2, 1 ],

       [ 3, 8, 6, 1, 3 ],

       [ -4, -1, 1, 7, -6 ],

       [ 0, -4, 10, -5, 1 ]];

         

print("Maximum Value is " + 

       str(findMaxValue(mat)))

        
# Этот код добавлен
# by ChitraNayal

C #

// Наивный метод, чтобы найти максимум
// значение mat [d] [e] - mat [a] [b]
// такой, что d> a и e> b

using System;

class GFG

{

      

    // функция возвращает

    // максимальное значение A (d, e) - A (a, b)

    // по всем вариантам индексов

    // такой, что оба d> a

    // и e> b.

    static int findMaxValue(int N, 

                            int [,]mat)

    {

          

        // сохраняет максимальное значение

        int maxValue = int.MinValue;

      

        // Рассмотрим все возможные пары

        // mat [a] [b] и mat [d] [e]

        for (int a = 0; a< N - 1; a++)

        for (int b = 0; b < N - 1; b++)

            for (int d = a + 1; d < N; d++)

            for (int e = b + 1; e < N; e++)

                if (maxValue < (mat[d, e] - 

                                mat[a, b]))

                    maxValue = mat[d, e] - 

                               mat[a, b];

  

        return maxValue;

    }

      

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

    public static void Main () 

    {

        int N = 5;

  

        int [,]mat = {{1, 2, -1, -4, -20},

                      {-8, -3, 4, 2, 1},

                      {3, 8, 6, 1, 3},

                      {-4, -1, 1, 7, -6},

                      {0, -4, 10, -5, 1}};

        Console.Write("Maximum Value is "

                      findMaxValue(N,mat));

    }

}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// Наивный метод, чтобы найти максимум
// значение $ mat [d] [e] - ma [a] [b]
// такой, что $ d> $ a и $ e> $ b

$N = 5;

  
// Функция возвращает максимум
// значение A (d, e) - A (a, b) более
// все варианты индексов такие
// что и $ d> $ a, и $ e> $ b.

function findMaxValue(&$mat)

{

    global $N;

      

    // сохраняет максимальное значение

    $maxValue = PHP_INT_MIN;

  

    // Рассмотрим все возможное

    // пары $ mat [$ a] [$ b] и

    // $ mat [$ d] [$ e]

    for ($a = 0; $a < $N - 1; $a++)

    for ($b = 0; $b < $N - 1; $b++)

        for ($d = $a + 1; $d < $N; $d++)

        for ($e = $b + 1; $e < $N; $e++)

            if ($maxValue < ($mat[$d][$e] - 

                             $mat[$a][$b]))

                $maxValue = $mat[$d][$e] - 

                            $mat[$a][$b];

  

    return $maxValue;

}

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

$mat = array(array(1, 2, -1, -4, -20),

             array(-8, -3, 4, 2, 1),

             array(3, 8, 6, 1, 3),

             array(-4, -1, 1, 7, -6),

             array(0, -4, 10, -5, 1));

              

echo "Maximum Value is "

       findMaxValue($mat);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Maximum Value is 18

Вышеприведенная программа выполняется за время O (n ^ 4), которое не близко к ожидаемой сложности времени O (n ^ 2)

Эффективное решение использует дополнительное пространство. Мы предварительно обрабатываем матрицу таким образом, чтобы индекс (i, j) сохранял максимальное количество элементов в матрице от (i, j) до (N-1, N-1) и в процессе продолжал обновлять максимальное найденное значение. Наконец мы возвращаем максимальное значение.

C ++

// Эффективный способ найти максимальное значение mat [d]
// - ma [a] [b] такой, что c> a и d> b
#include <bits/stdc++.h>

using namespace std;

#define N 5

  
// Функция возвращает максимальное значение A (c, d) - A (a, b)
// по всем вариантам индексов, так что оба c> a
// и d> b.

int findMaxValue(int mat[][N])

{

    // сохраняет максимальное значение

    int maxValue = INT_MIN;

  

    // maxArr [i] [j] сохраняет максимум элементов в матрице

    // из (i, j) в (N-1, N-1)

    int maxArr[N][N];

  

    // последний элемент maxArr будет таким же, как

    // матрица ввода

    maxArr[N-1][N-1] = mat[N-1][N-1];

  

    // предварительная обработка последней строки

    int maxv = mat[N-1][N-1];  // Инициализировать макс

    for (int j = N - 2; j >= 0; j--)

    {

        if (mat[N-1][j] > maxv)

            maxv = mat[N - 1][j];

        maxArr[N-1][j] = maxv;

    }

  

    // предварительная обработка последнего столбца

    maxv = mat[N - 1][N - 1];  // Инициализировать макс

    for (int i = N - 2; i >= 0; i--)

    {

        if (mat[i][N - 1] > maxv)

            maxv = mat[i][N - 1];

        maxArr[i][N - 1] = maxv;

    }

  

    // препроцесс остальной матрицы снизу

    for (int i = N-2; i >= 0; i--)

    {

        for (int j = N-2; j >= 0; j--)

        {

            // Обновляем maxValue

            if (maxArr[i+1][j+1] - mat[i][j] >

                                            maxValue)

                maxValue = maxArr[i + 1][j + 1] - mat[i][j];

  

            // установить maxArr (i, j)

            maxArr[i][j] = max(mat[i][j],

                               max(maxArr[i][j + 1],

                                   maxArr[i + 1][j]) );

        }

    }

  

    return maxValue;

}

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

int main()

{

    int mat[N][N] = {

                      { 1, 2, -1, -4, -20 },

                      { -8, -3, 4, 2, 1 },

                      { 3, 8, 6, 1, 3 },

                      { -4, -1, 1, 7, -6 },

                      { 0, -4, 10, -5, 1 }

                    };

    cout << "Maximum Value is " 

         << findMaxValue(mat);

  

    return 0;

}

Джава

// Эффективный способ найти максимальное значение mat1 [d]
// - ma [a] [b] такой, что c> a и d> b

import java.io.*;

import java.util.*;

   

class GFG 

{

    // Функция возвращает максимальное значение A (c, d) - A (a, b)

    // по всем вариантам индексов, так что оба c> a

    // и d> b.

    static int findMaxValue(int N,int mat[][])

    {

        // сохраняет максимальное значение

        int maxValue = Integer.MIN_VALUE;

       

        // maxArr [i] [j] сохраняет максимум элементов в матрице

        // из (i, j) в (N-1, N-1)

        int maxArr[][] = new int[N][N];

       

        // последний элемент maxArr будет таким же, как

        // матрица ввода

        maxArr[N-1][N-1] = mat[N-1][N-1];

       

        // предварительная обработка последней строки

        int maxv = mat[N-1][N-1];  // Инициализировать макс

        for (int j = N - 2; j >= 0; j--)

        {

            if (mat[N-1][j] > maxv)

                maxv = mat[N - 1][j];

            maxArr[N-1][j] = maxv;

        }

       

        // предварительная обработка последнего столбца

        maxv = mat[N - 1][N - 1];  // Инициализировать макс

        for (int i = N - 2; i >= 0; i--)

        {

            if (mat[i][N - 1] > maxv)

                maxv = mat[i][N - 1];

            maxArr[i][N - 1] = maxv;

        }

       

        // препроцесс остальной матрицы снизу

        for (int i = N-2; i >= 0; i--)

        {

            for (int j = N-2; j >= 0; j--)

            {

                // Обновляем maxValue

                if (maxArr[i+1][j+1] - mat[i][j] > maxValue)

                    maxValue = maxArr[i + 1][j + 1] - mat[i][j];

       

                // установить maxArr (i, j)

                maxArr[i][j] = Math.max(mat[i][j],

                                   Math.max(maxArr[i][j + 1],

                                       maxArr[i + 1][j]) );

            }

        }

       

        return maxValue;

    }

      

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

    public static void main (String[] args) 

    {

        int N = 5;

  

        int mat[][] = {

                      { 1, 2, -1, -4, -20 },

                      { -8, -3, 4, 2, 1 },

                      { 3, 8, 6, 1, 3 },

                      { -4, -1, 1, 7, -6 },

                      { 0, -4, 10, -5, 1 }

                   };

  

        System.out.print("Maximum Value is "

                           findMaxValue(N,mat));

    }

}

   
// Предоставлено Пракрити Гупта

python3

# Эффективный способ найти максимальное значение
количество матов [d] - ma [a] [b], таких что c> a и d> b

  

import sys

N = 5

  
# Функция возвращает максимальное значение
# A (c, d) - A (a, b) по всем вариантам
# индексы такие, что оба c> a и d> b.

def findMaxValue(mat):

  

    # хранит максимальное значение

    maxValue = -sys.maxsize -1

  

    # maxArr [i] [j] хранит максимум элементов

    # в матрице от (i, j) до (N-1, N-1)

    maxArr = [[0 for x in range(N)]

                 for y in range(N)]

  

    # последний элемент maxArr будет

    # столько же, сколько во входной матрице

    maxArr[N - 1][N - 1] = mat[N - 1][N - 1]

  

    # препроцесс последней строки

    maxv = mat[N - 1][N - 1]; # Initialize max

    for j in range (N - 2, -1, -1):

      

        if (mat[N - 1][j] > maxv):

            maxv = mat[N - 1][j]

        maxArr[N - 1][j] = maxv

      

    # предварительная обработка последнего столбца

    maxv = mat[N - 1][N - 1] # Initialize max

    for i in range (N - 2, -1, -1):

      

        if (mat[i][N - 1] > maxv):

            maxv = mat[i][N - 1]

        maxArr[i][N - 1] = maxv

  

    # препроцесс остальной матрицы

    # снизу

    for i in range (N - 2, -1, -1):

      

        for j in range (N - 2, -1, -1):

          

            # Обновление maxValue

            if (maxArr[i + 1][j + 1] -

                mat[i][j] > maxValue):

                maxValue = (maxArr[i + 1][j + 1] - 

                                       mat[i][j])

  

            # set maxArr (i, j)

            maxArr[i][j] = max(mat[i][j], 

                           max(maxArr[i][j + 1], 

                               maxArr[i + 1][j]))

          

    return maxValue

  
Код водителя

mat = [[ 1, 2, -1, -4, -20 ],

       [-8, -3, 4, 2, 1 ],

       [ 3, 8, 6, 1, 3 ],

       [ -4, -1, 1, 7, -6] ,

       [0, -4, 10, -5, 1 ]]

                      

print ("Maximum Value is",

        findMaxValue(mat))

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

C #

// Эффективный способ найти
// максимальное значение mat1 [d]
// - ma [a] [b] такой, что c> a
// и d> b

using System;

class GFG  {

      

    // функция возвращает

    // максимальное значение A (c, d) - A (a, b)

    // по всем вариантам индексов

    // такой, что оба c> a

    // и d> b.

    static int findMaxValue(int N, int [,]mat)

    {

          

        // сохраняет максимальное значение

        int maxValue = int.MinValue;

      

        // maxArr [i] [j] сохраняет максимум

        // элементов в матрице

        // из (i, j) в (N-1, N-1)

        int [,]maxArr = new int[N, N];

      

        // последний элемент maxArr

        // будет таким же, как и

        // матрица ввода

        maxArr[N - 1, N - 1] = mat[N - 1,N - 1];

      

        // предварительная обработка последней строки

         // Инициализировать макс

        int maxv = mat[N - 1, N - 1];

        for (int j = N - 2; j >= 0; j--)

        {

            if (mat[N - 1, j] > maxv)

                maxv = mat[N - 1, j];

            maxArr[N - 1, j] = maxv;

        }

      

        // предварительная обработка последнего столбца

        // Инициализировать макс

        maxv = mat[N - 1,N - 1]; 

        for (int i = N - 2; i >= 0; i--)

        {

            if (mat[i, N - 1] > maxv)

                maxv = mat[i,N - 1];

            maxArr[i,N - 1] = maxv;

        }

      

        // препроцесс остальной части

        // матрица снизу

        for (int i = N - 2; i >= 0; i--)

        {

            for (int j = N - 2; j >= 0; j--)

            {

                  

                // Обновляем maxValue

                if (maxArr[i + 1,j + 1] - 

                     mat[i, j] > maxValue)

                    maxValue = maxArr[i + 1,j + 1] - 

                                         mat[i, j];

      

                // установить maxArr (i, j)

                maxArr[i,j] = Math.Max(mat[i, j],

                              Math.Max(maxArr[i, j + 1],

                              maxArr[i + 1, j]) );

            }

        }

      

        return maxValue;

    }

      

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

    public static void Main () 

    {

        int N = 5;

  

        int [,]mat = {{ 1, 2, -1, -4, -20 },

                      { -8, -3, 4, 2, 1 },

                      { 3, 8, 6, 1, 3 },

                      { -4, -1, 1, 7, -6 },

                      { 0, -4, 10, -5, 1 }};

        Console.Write("Maximum Value is "

                        findMaxValue(N,mat));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php 
// Эффективный способ найти
// максимальное значение mat [d] - ma [a] [b]
// такой, что c> a и d> b

$N = 5;

  
// Функция возвращает максимум
// значение A (c, d) - A (a, b) более
// все варианты индексов такие
// что и c> a, и d> b.

function findMaxValue($mat)

{

    global $N;

      

    // сохраняет максимальное значение

    $maxValue = PHP_INT_MIN;

  

    // maxArr [i] [j] сохраняет максимум

    // элементов в матрице

    // из (i, j) в (N-1, N-1)

    $maxArr[$N][$N] = array();

  

    // последний элемент maxArr

    // будет таким же, как и

    // матрица ввода

    $maxArr[$N - 1][$N - 1] = $mat[$N - 1][$N - 1];

  

    // предварительная обработка последней строки

    $maxv = $mat[$N - 1][$N - 1]; // Инициализировать макс

    for ($j = $N - 2; $j >= 0; $j--)

    {

        if ($mat[$N - 1][$j] > $maxv)

            $maxv = $mat[$N - 1][$j];

        $maxArr[$N - 1][$j] = $maxv;

    }

  

    // предварительная обработка последнего столбца

    $maxv = $mat[$N - 1][$N - 1]; // Инициализировать макс

    for ($i = $N - 2; $i >= 0; $i--)

    {

        if ($mat[$i][$N - 1] > $maxv)

            $maxv = $mat[$i][$N - 1];

        $maxArr[$i][$N - 1] = $maxv;

    }

  

    // препроцесс остальной части

    // матрица снизу

    for ($i = $N - 2; $i >= 0; $i--)

    {

        for ($j = $N - 2; $j >= 0; $j--)

        {

            // Обновляем maxValue

            if ($maxArr[$i + 1][$j + 1] - 

                $mat[$i][$j] > $maxValue)

                $maxValue = $maxArr[$i + 1][$j + 1] - 

                            $mat[$i][$j];

  

            // установить maxArr (i, j)

            $maxArr[$i][$j] = max($mat[$i][$j],

                              max($maxArr[$i][$j + 1],

                                  $maxArr[$i + 1][$j]));

        }

    }

  

    return $maxValue;

}

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

$mat = array(array(1, 2, -1, -4, -20),

             array(-8, -3, 4, 2, 1),

             array(3, 8, 6, 1, 3),

             array(-4, -1, 1, 7, -6),

             array(0, -4, 10, -5, 1)

                    );

echo "Maximum Value is "

      findMaxValue($mat);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Maximum Value is 18

Если нам разрешено изменять матрицу, мы можем избежать использования дополнительного пространства и использовать вместо нее матрицу ввода.

Упражнение: Напечатайте также индексы (a, b) и (c, d).

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

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

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

Найти конкретную пару в матрице

0.00 (0%) 0 votes