Рубрики

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

Учитывая матрицу размера 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];

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

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;

}

Выход:

28

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

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

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

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

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

0.00 (0%) 0 votes