Dada una array de tamaño nxn, encuentre la suma de la secuencia Zigzag con la suma más grande. Una secuencia en zigzag comienza en la parte superior y termina en la parte inferior. Dos elementos consecutivos de secuencia no pueden pertenecer a la misma columna.
Ejemplos:
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
Este problema tiene una subestructura óptima .
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
Implementación:
C++
// C++ program to find the largest sum zigzag sequence
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Returns largest sum of a Zigzag sequence starting
// from (i, j) and ending at a bottom cell.
int largestZigZagSumRec(int mat[][MAX], int i,
int j, int n)
{
// If we have reached bottom
if (i == n-1)
return mat[i][j];
// Find the largest sum by considering all
// possible next elements in sequence.
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];
}
// Returns largest possible sum of a Zigzag sequence
// starting from top and ending at bottom.
int largestZigZag(int mat[][MAX], int n)
{
// Consider all cells of top row as starting point
int res = 0;
for (int j=0; j<n; j++)
res = max(res, largestZigZagSumRec(mat, 0, j, n));
return res;
}
// Driver program to test above
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
// Java program to find the largest sum
// zigzag sequence
import java.io.*;
class GFG {
static int MAX = 100;
// Returns largest sum of a Zigzag
// sequence starting from (i, j)
// and ending at a bottom cell.
static int largestZigZagSumRec(int mat[][],
int i, int j, int n)
{
// If we have reached bottom
if (i == n-1)
return mat[i][j];
// Find the largest sum by considering all
// possible next elements in sequence.
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];
}
// Returns largest possible sum of a Zigzag
// sequence starting from top and ending
// at bottom.
static int largestZigZag(int mat[][], int n)
{
// Consider all cells of top row as starting
// point
int res = 0;
for (int j=0; j<n; j++)
res = Math.max(res,
largestZigZagSumRec(mat, 0, j, n));
return res;
}
// Driver program to test above
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));
}
}
// This code is contributed by anuj_67.
Python 3
# Python3 program to find the largest
# sum zigzag sequence
MAX = 100
# Returns largest sum of a Zigzag
# sequence starting from (i, j) and
# ending at a bottom cell.
def largestZigZagSumRec( mat, i, j, n):
# If we have reached bottom
if (i == n-1):
return mat[i][j]
# Find the largest sum by considering all
# possible next elements in sequence.
zzs = 0
for k in range(n):
if (k != j):
zzs = max(zzs, largestZigZagSumRec(mat, i + 1, k, n))
return zzs + mat[i][j]
# Returns largest possible sum of a
# Zigzag sequence starting from top
# and ending at bottom.
def largestZigZag(mat, n):
# Consider all cells of top row as
# starting point
res = 0
for j in range(n):
res = max(res, largestZigZagSumRec(mat, 0, j, n))
return res
# Driver Code
if __name__ == "__main__":
n = 3
mat = [ [4, 2, 1],
[3, 9, 6],
[11, 3, 15]]
print("Largest zigzag sum: " ,
largestZigZag(mat, n))
# This code is contributed by ChitraNayal
C#
// C# program to find the largest sum
// zigzag sequence
using System;
class GFG {
// static int MAX = 100;
// Returns largest sum of a Zigzag
// sequence starting from (i, j)
// and ending at a bottom cell.
static int largestZigZagSumRec(int [,]mat,
int i, int j, int n)
{
// If we have reached bottom
if (i == n-1)
return mat[i,j];
// Find the largest sum by considering all
// possible next elements in sequence.
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];
}
// Returns largest possible
// sum of a Zigzag sequence
// starting from top and ending
// at bottom.
static int largestZigZag(int [,]mat, int n)
{
// Consider all cells of
// top row as starting
// point
int res = 0;
for (int j = 0; j < n; j++)
res = Math.Max(res,
largestZigZagSumRec(mat, 0, j, n));
return res;
}
// Driver Code
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));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find the
// largest sum zigzag sequence
$MAX = 100;
// Returns largest sum of a
// Zigzag sequence starting
// from (i, j) and ending at
// a bottom cell.
function largestZigZagSumRec($mat, $i,
$j, $n)
{
// If we have reached bottom
if ($i == $n - 1)
return $mat[$i][$j];
// Find the largest sum
// by considering all
// possible next elements
// in sequence.
$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];
}
// Returns largest possible
// sum of a Zigzag sequence
// starting from top and
// ending at bottom.
function largestZigZag( $mat, $n)
{
// Consider all cells of top
// row as starting point
$res = 0;
for ($j = 0; $j < $n; $j++)
$res = max($res, largestZigZagSumRec(
$mat, 0, $j, $n));
return $res;
}
// Driver Code
$n = 3;
$mat = array(array(4, 2, 1),
array(3, 9, 6),
array(11, 3, 15));
echo "Largest zigzag sum: " , largestZigZag($mat, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find the largest sum
// zigzag sequence
let MAX = 100;
// Returns largest sum of a Zigzag
// sequence starting from (i, j)
// and ending at a bottom cell.
function largestZigZagSumRec(mat,i,j,n)
{
// If we have reached bottom
if (i == n-1)
return mat[i][j];
// Find the largest sum by considering all
// possible next elements in sequence.
let zzs = 0;
for (let k=0; k<n; k++)
if (k != j)
zzs = Math.max(zzs,
largestZigZagSumRec(mat, i+1, k, n));
return zzs + mat[i][j];
}
// Returns largest possible sum of a Zigzag
// sequence starting from top and ending
// at bottom.
function largestZigZag(mat,n)
{
// Consider all cells of top row as starting
// point
let res = 0;
for (let j=0; j<n; j++)
res = Math.max(res,
largestZigZagSumRec(mat, 0, j, n));
return res;
}
// Driver program to test above
let n = 3;
let mat = [ [4, 2, 1],
[3, 9, 6],
[11, 3, 15]];
document.write("Largest zigzag sum: " +
largestZigZag(mat, n))
// This code is contributed by rag2127
</script>
Producción
Largest zigzag sum: 28
Subproblemas superpuestos
Considerando la implementación anterior, para una array mat[][] de tamaño 3 x 3, para encontrar la suma en zigzag(zzs) para un elemento mat(i,j), se forma el siguiente árbol de recurrencia.
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)
Podemos ver que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene la propiedad de subestructura superpuesta y el recálculo de los mismos subproblemas se puede evitar mediante Memoización o Tabulación. A continuación se muestra una implementación tabulada para el problema LIS.
Implementación:
C++
// Memoization based C++ program to find the largest
// sum zigzag sequence
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int dp[MAX][MAX];
// Returns largest sum of a Zigzag sequence starting
// from (i, j) and ending at a bottom cell.
int largestZigZagSumRec(int mat[][MAX], int i,
int j, int n)
{
if (dp[i][j] != -1)
return dp[i][j];
// If we have reached bottom
if (i == n-1)
return (dp[i][j] = mat[i][j]);
// Find the largest sum by considering all
// possible next elements in sequence.
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]));
}
// Returns largest possible sum of a Zigzag sequence
// starting from top and ending at bottom.
int largestZigZag(int mat[][MAX], int n)
{
memset(dp, -1, sizeof(dp));
// Consider all cells of top row as starting point
int res = 0;
for (int j=0; j<n; j++)
res = max(res, largestZigZagSumRec(mat, 0, j, n));
return res;
}
// Driver program to test above
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
// Memoization based Java program to find the largest
// sum zigzag sequence
class GFG
{
static int MAX = 100;
static int [][]dp = new int[MAX][MAX];
// Returns largest sum of a Zigzag sequence starting
// from (i, j) and ending at a bottom cell.
static int largestZigZagSumRec(int mat[][], int i,
int j, int n)
{
if (dp[i][j] != -1)
return dp[i][j];
// If we have reached bottom
if (i == n - 1)
return (dp[i][j] = mat[i][j]);
// Find the largest sum by considering all
// possible next elements in sequence.
int zzs = 0;
for (int k = 0; k < n; k++)
if (k != j)
zzs = Math.max(zzs, largestZigZagSumRec(mat,
i + 1, k, n));
return (dp[i][j] = (zzs + mat[i][j]));
}
// Returns largest possible sum of a Zigzag sequence
// starting from top and ending at bottom.
static int largestZigZag(int mat[][], int n)
{
for (int i = 0; i < MAX; i++)
for (int k = 0; k < MAX; k++)
dp[i][k] = -1;
// Consider all cells of top row as starting point
int res = 0;
for (int j = 0; j < n; j++)
res = Math.max(res, largestZigZagSumRec(mat,
0, j, n));
return res;
}
// Driver code
public static void main(String[] args)
{
int n = 3;
int mat[][] = { {4, 2, 1},
{3, 9, 6},
{11, 3, 15}};
System.out.print("Largest zigzag sum: " +
largestZigZag(mat, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Memoization based Python3 program to find the largest
# sum zigzag sequence
MAX = 100;
dp = [[0 for i in range(MAX)] for j in range(MAX)]
# Returns largest sum of a Zigzag sequence starting
# from (i, j) and ending at a bottom cell.
def largestZigZagSumRec(mat, i, j, n):
if (dp[i][j] != -1):
return dp[i][j];
# If we have reached bottom
if (i == n - 1):
dp[i][j] = mat[i][j];
return (dp[i][j]);
# Find the largest sum by considering all
# possible next elements in sequence.
zzs = 0;
for k in range(n):
if (k != j):
zzs = max(zzs, largestZigZagSumRec(mat,
i + 1, k, n));
dp[i][j] = (zzs + mat[i][j]);
return (dp[i][j]);
# Returns largest possible sum of a Zigzag sequence
# starting from top and ending at bottom.
def largestZigZag(mat, n):
for i in range(MAX):
for k in range(MAX):
dp[i][k] = -1;
# Consider all cells of top row as starting point
res = 0;
for j in range(n):
res = max(res, largestZigZagSumRec(mat, 0, j, n));
return res;
# Driver code
if __name__ == '__main__':
n = 3;
mat = [[4, 2, 1], [3, 9, 6], [11, 3, 15]];
print("Largest zigzag sum: ", largestZigZag(mat, n));
# This code is contributed by Rajput-Ji
C#
// Memoization based C# program to find the largest
// sum zigzag sequence
using System;
class GFG
{
static int MAX = 100;
static int [,]dp = new int[MAX, MAX];
// Returns largest sum of a Zigzag sequence starting
// from (i, j) and ending at a bottom cell.
static int largestZigZagSumRec(int [,]mat, int i,
int j, int n)
{
if (dp[i, j] != -1)
return dp[i, j];
// If we have reached bottom
if (i == n - 1)
return (dp[i, j] = mat[i, j]);
// Find the largest sum by considering all
// possible next elements in sequence.
int zzs = 0;
for (int k = 0; k < n; k++)
if (k != j)
zzs = Math.Max(zzs, largestZigZagSumRec(mat,
i + 1, k, n));
return (dp[i, j] = (zzs + mat[i, j]));
}
// Returns largest possible sum of a Zigzag sequence
// starting from top and ending at bottom.
static int largestZigZag(int [,]mat, int n)
{
for (int i = 0; i < MAX; i++)
for (int k = 0; k < MAX; k++)
dp[i, k] = -1;
// Consider all cells of top row as starting point
int res = 0;
for (int j = 0; j < n; j++)
res = Math.Max(res, largestZigZagSumRec(mat,
0, j, n));
return res;
}
// Driver code
public static void Main(String[] args)
{
int n = 3;
int [,]mat = { {4, 2, 1},
{3, 9, 6},
{11, 3, 15}};
Console.Write("Largest zigzag sum: " +
largestZigZag(mat, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Memoization based Javascript program to find the largest
// sum zigzag sequence
let MAX = 100;
let dp=new Array(MAX);
// Returns largest sum of a Zigzag sequence starting
// from (i, j) and ending at a bottom cell.
function largestZigZagSumRec(mat,i,j,n)
{
if (dp[i][j] != -1)
return dp[i][j];
// If we have reached bottom
if (i == n - 1)
return (dp[i][j] = mat[i][j]);
// Find the largest sum by considering all
// possible next elements in sequence.
let zzs = 0;
for (let k = 0; k < n; k++)
if (k != j)
zzs = Math.max(zzs, largestZigZagSumRec(mat,
i + 1, k, n));
return (dp[i][j] = (zzs + mat[i][j]));
}
// Returns largest possible sum of a Zigzag sequence
// starting from top and ending at bottom.
function largestZigZag(mat,n)
{
for (let i = 0; i < MAX; i++)
{
dp[i]=new Array(MAX);
for (let k = 0; k < MAX; k++)
dp[i][k] = -1;
}
// Consider all cells of top row as starting point
let res = 0;
for (let j = 0; j < n; j++)
res = Math.max(res, largestZigZagSumRec(mat,
0, j, n));
return res;
}
// Driver code
let n = 3;
let mat=[[4, 2, 1],[3, 9, 6],[11, 3, 15]];
document.write("Largest zigzag sum: " +
largestZigZag(mat, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Largest zigzag sum: 28
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA