Самая большая сумма зигзагообразной последовательности в матрице

31.12.2019Динамическое программирование, Матрицы

Учитывая матрицу размера nxn, найдите сумму зигзагообразной последовательности с наибольшей суммой. Зигзагообразная последовательность начинается сверху и заканчивается снизу. Два последовательных элемента последовательности не могут принадлежать одному столбцу.
Примеры:

Input : mat[][] = 3  1  2
                  4  8  5
                  6  9  7
Output : 18
Zigzag sequence is: 3->8->7
Another such sequence is 2->4->7

Input : mat[][] =  4  2  1
                   3  9  6
                  11  3 15
Output : 28

Эта проблема имеет Оптимальную Подструктуру .

Maximum Zigzag sum starting from arr[i][j] to a 
bottom cell can be written as :
zzs(i, j) = arr[i][j] + max(zzs(i+1, k)), 
               where k = 0, 1, 2 and k != j
zzs(i, j) = arr[i][j], if i = n-1 

We have to find the largest among all as
Result = zzs(0, j) where 0 <= j < n

C ++

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

using namespace std;

const int MAX = 100;

// Возвращает наибольшую сумму начала зигзагообразной последовательности
// из (i, j) и заканчивается в нижней ячейке.

int largestZigZagSumRec(int mat[][MAX], int i,

int j, int n)

{

// Если мы достигли дна

if (i == n-1)

return mat[i][j];

// Найти наибольшую сумму, учитывая все

// возможны следующие элементы в последовательности.

int zzs = 0;

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

if (k != j)

zzs = max(zzs, largestZigZagSumRec(mat, i+1, k, n));

return zzs + mat[i][j];

}

// Возвращает максимально возможную сумму последовательности Zizag
// начиная сверху и заканчивая снизу.

int largestZigZag(int mat[][MAX], int n)

{

// Рассмотрим все ячейки верхнего ряда как отправную точку

int res = 0;

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

res = max(res, largestZigZagSumRec(mat, 0, j, n));

return res;

}

// Программа драйвера для тестирования выше

int main()

{

int n = 3;

int mat[][MAX] = { {4, 2, 1},

{3, 9, 6},

{11, 3, 15}};

cout << "Largest zigzag sum: " << largestZigZag(mat, n);

return 0;

}

Джава

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

import java.io.*;

class GFG {

static int MAX = 100;

// Возвращает наибольшую сумму зигзага

// последовательность начинается с (i, j)

// и заканчивается в нижней ячейке.

static int largestZigZagSumRec(int mat[][],

int i, int j, int n)

{

// Если мы достигли дна

if (i == n-1)

return mat[i][j];

// Найти наибольшую сумму, учитывая все

// возможны следующие элементы в последовательности.

int zzs = 0;

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

if (k != j)

zzs = Math.max(zzs,

largestZigZagSumRec(mat, i+1, k, n));

return zzs + mat[i][j];

}

// Возвращает максимально возможную сумму Zizag

// последовательность, начинающаяся с вершины и заканчивающаяся

// на дне.

static int largestZigZag(int mat[][], int n)

{

// Рассмотрим все ячейки верхнего ряда как начальные

// точка

int res = 0;

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

res = Math.max(res,

largestZigZagSumRec(mat, 0, j, n));

return res;

}

// Программа драйвера для тестирования выше

public static void main (String[] args)

{

int n = 3;

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

{3, 9, 6},

{11, 3, 15} };

System.out.println( "Largest zigzag sum: "

+ largestZigZag(mat, n));

}

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

Python 3

# Python3 программа для поиска самых больших
# сумма зигзагообразной последовательности

MAX = 100

# Возвращает наибольшую сумму зигзага
# последовательность, начинающаяся с (i, j) и
# заканчивается в нижней ячейке.

def largestZigZagSumRec( mat, i, j, n):

# Если мы достигли дна

if (i == n-1):

return mat[i][j]

# Найти наибольшую сумму, учитывая все

# возможные следующие элементы в последовательности.

zzs = 0

for k in range(n):

if (k != j):

zzs = max(zzs, largestZigZagSumRec(mat, i + 1, k, n))

return zzs + mat[i][j]

# Возвращает максимально возможную сумму
# Последовательность Zizag, начиная с вершины
# и заканчивается снизу.

def largestZigZag(mat, n):

# Рассмотрим все ячейки верхнего ряда как

# отправная точка

res = 0

for j in range(n):

res = max(res, largestZigZagSumRec(mat, 0, j, n))

return res

Код водителя

if __name__ == "__main__":

n = 3

mat = [ [4, 2, 1],

[3, 9, 6],

[11, 3, 15]]

print("Largest zigzag sum: " ,

largestZigZag(mat, n))

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

C #

// C # программа для поиска наибольшей суммы
// зигзагообразная последовательность

using System;

class GFG {

// static int MAX = 100;

// Возвращает наибольшую сумму зигзага

// последовательность начинается с (i, j)

// и заканчивается в нижней ячейке.

static int largestZigZagSumRec(int [,]mat,

int i, int j, int n)

{

// Если мы достигли дна

if (i == n-1)

return mat[i,j];

// Найти наибольшую сумму, учитывая все

// возможны следующие элементы в последовательности.

int zzs = 0;

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

if (k != j)

zzs = Math.Max(zzs, largestZigZagSumRec(mat,

i + 1, k, n));

return zzs + mat[i,j];

}

// Возвращает максимально возможный

// сумма последовательности Зизага

// начиная с вершины и заканчивая

// на дне.

static int largestZigZag(int [,]mat, int n)

{

// Рассмотрим все ячейки

// верхняя строка как стартовая

// точка

int res = 0;

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

res = Math.Max(res,

largestZigZagSumRec(mat, 0, j, n));

return res;

}

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

public static void Main ()

{

int n = 3;

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

{3, 9, 6},

{11, 3, 15}};

Console.WriteLine("Largest zigzag sum: "

+ largestZigZag(mat, n));

}

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

PHP

<?php
// PHP программа для поиска
// наибольшая сумма зигзагообразной последовательности

$MAX = 100;

// Возвращает наибольшую сумму
// Зигзагообразная последовательность запуска
// из (i, j) и заканчивая в
// нижняя ячейка

function largestZigZagSumRec($mat, $i,

$j, $n)

{

// Если мы достигли дна

if ($i == $n - 1)

return $mat[$i][$j];

// Находим наибольшую сумму

// учитывая все

// возможны следующие элементы

// по порядку.

$zzs = 0;

for ($k = 0; $k < $n; $k++)

if ($k != $j)

$zzs = max($zzs, largestZigZagSumRec($mat,

$i + 1, $k, $n));

return $zzs + $mat[$i][$j];

}

// Возвращает максимально возможный
// сумма последовательности Зизага
// начиная сверху и
// заканчивается снизу.

function largestZigZag( $mat, $n)

{

// Рассмотрим все ячейки сверху

// строка в качестве отправной точки

$res = 0;

for ($j = 0; $j < $n; $j++)

$res = max($res, largestZigZagSumRec(

$mat, 0, $j, $n));

return $res;

}

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

$n = 3;

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

array(3, 9, 6),

array(11, 3, 15));

echo "Largest zigzag sum: " , largestZigZag($mat, $n);

// Этот код предоставлен anuj_67.
?>

Выход:

Largest zigzag sum: 28

Перекрывающиеся подзадачи
Учитывая вышеприведенную реализацию, для матрицы mat [] [] размером 3 x 3, чтобы найти зигзагообразную сумму (zzs) для элемента mat (i, j), формируется следующее дерево рекурсии.

Recursion tree for cell (0, 0)
             zzs(0,0)                                
           /         \                               
    zzs(1,1)           zzs(1,2)                      
    /     \            /      \                      
zzs(2,0)  zzs(2,2)  zzs(2,0)  zzs(2,1)               


Recursion tree for cell (0, 1)
            zzs(0,1)
           /         \              
    zzs(1,0)          zzs(1,2)
    /     \            /      \    
zzs(2,1)  zzs(2,2)  zzs(2,0)  zzs(2,1)

Recursion tree for cell (0, 2)
             zzs(0,2)
           /         \                                             
    zzs(1,0)           zzs(1,1)                             
    /     \            /      \                             
 zzs(2,1)  zzs(2,2)  zzs(2,0)  zzs(2,2)

Мы видим, что есть много подзадач, которые решаются снова и снова. Таким образом, эта проблема имеет свойство «Перекрывающаяся подструктура», и повторного вычисления тех же подзадач можно избежать, используя Memoization или Tabulation. Ниже приведена табличная реализация проблемы LIS.

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

using namespace std;

const int MAX = 100;

int dp[MAX][MAX];

int largestZigZagSumRec(int mat[][MAX], int i,

int j, int n)

{

if (dp[i][j] != -1)

return dp[i][j];

// Если мы достигли дна

if (i == n-1)

return (dp[i][j] = mat[i][j]);

// Найти наибольшую сумму, учитывая все

// возможны следующие элементы в последовательности.

int zzs = 0;

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

if (k != j)

zzs = max(zzs, largestZigZagSumRec(mat, i+1, k, n));

return (dp[i][j] = (zzs + mat[i][j]));

}

// Возвращает максимально возможную сумму последовательности Zizag
// начиная сверху и заканчивая снизу.

int largestZigZag(int mat[][MAX], int n)

{

memset(dp, -1, sizeof(dp));

// Рассмотрим все ячейки верхнего ряда как отправную точку

int res = 0;

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

res = max(res, largestZigZagSumRec(mat, 0, j, n));

return res;

}

// Программа драйвера для тестирования выше

int main()

{

int n = 3;

int mat[][MAX] = { {4, 2, 1},

{3, 9, 6},

{11, 3, 15}};

cout << "Largest zigzag sum: " << largestZigZag(mat, n);

return 0;

}

Выход:

Рекомендации: Спросил в Directi

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

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

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

Самая большая сумма зигзагообразной последовательности в матрице

0.00 (0%) 0 votes