Suma máxima de elementos en una diagonal paralela a la diagonal principal de una Array dada

Dé una array cuadrada mat[][] de dimensiones N * N , la tarea es encontrar la suma máxima de elementos presentes en la array dada a lo largo de las diagonales que son paralelas a la diagonal principal. A continuación se muestra la imagen del mismo.

Ejemplos: 

Entrada: mat[][] = {{1, 2, 5, 7}, {2, 6, 7, 3}, {12, 3, 2, 4}, {3, 6, 9, 4}}
Salida : 18
Explicación:
La suma de los elementos presentes en la diagonal que tiene celdas (2, 0) y (3, 1) es 12 + 6 = 18 que es el máximo entre todas las diagonales.

Entrada: mat[][] = {{5, 2, 5, 7}, {2, 5, 7, 3}, {12, 3, 5, 4}, {3, 6, 9, 5}}
Salida : 18
Explicación:
La suma de los elementos presentes en la diagonal principal que tiene celdas (0, 0), (1, 1), (2, 2) y (3, 3) es 5 + 5 + 5 + 5 = 20 que es el máximo entre todas las diagonales.

Enfoque: la idea es atravesar las celdas de cada diagonal que es paralela a la diagonal principal y observar que para cualquier diagonal por encima de la diagonal principal que comience en la celda (x, y) , su diagonal correspondiente que está debajo de la diagonal principal comenzará en la celda (y, x) . Para cada diagonal, comenzando en la celda (x, y) todos sus elementos estarán en las celdas (x + k, y + k) donde 0 <= x + k, y + k < N . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable maxSum con 0 que almacenará la suma diagonal máxima.
• Atraviese las columnas de ^la fila 0 desde i sobre el rango [0, N – 1] .
• Inicialice las variables sum1 y sum2 que almacenarán las sumas diagonales a partir de la celda (fila, columna) y de la celda (columna, fila) respectivamente, donde r es 0 y c es columna .
• Incremente tanto la fila como c en 1 . Agregue mat[row][col] a sum1 y mat[col][row] a sum2 mientras que row y col son más pequeños que N . Finalmente, actualice maxSum para almacenar el máximo de maxSum, sum1 y sum2 .
• Después de atravesar la array dada, imprima el valor maxSum como la suma máxima.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return maximum diagonal
// sum that are parallel to main diagonal
int maxDiagonalSum(vector<vector<int> > arr, int N)
{
    // Initialize maxSum
    int maxSum = 0;
 
    // Traverse through the columns
    for (int i = 0; i < N; i++) {
 
        // Initialize r and c
        int row = 0, col = i;
 
        // Diagonal sums
        int sum1 = 0, sum2 = 0;
        while (col < N && row < N) {
            sum1 += arr[row][col];
            sum2 += arr[col][row];
            row++;
            col++;
        }
 
        // Update maxSum with
        // the maximum sum
        maxSum = max({ sum1, maxSum, sum2 });
    }
 
    // Return the maxSum
    return maxSum;
}
 
// Driver Code
int main()
{
    // Given matrix mat[][]
    vector<vector<int> > mat
        = { { 1, 2, 5, 7 },
            { 2, 6, 7, 3 },
            { 12, 3, 2, 4 },
            { 3, 6, 9, 4 } };
    int N = mat.size();
 
    // Function Call
    cout << maxDiagonalSum(mat, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
   
// Function to return maximum diagonal
// sum that are parallel to main diagonal
static int maxDiagonalSum(int arr[][], int N)
{
     
    // Initialize maxSum
    int maxSum = 0;
 
    // Traverse through the columns
    for(int i = 0; i < N; i++)
    {
         
        // Initialize r and c
        int row = 0, col = i;
 
        // Diagonal sums
        int sum1 = 0, sum2 = 0;
        while (col < N && row < N)
        {
            sum1 += arr[row][col];
            sum2 += arr[col][row];
            row++;
            col++;
        }
 
        // Update maxSum with
        // the maximum sum
        maxSum = Math.max(maxSum,
                          Math.max(sum1,
                                   sum2));
    }
 
    // Return the maxSum
    return maxSum;
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given matrix mat[][]
    int mat[][] = { { 1, 2, 5, 7 },
                    { 2, 6, 7, 3 },
                    { 12, 3, 2, 4 },
                    { 3, 6, 9, 4 } };
    int N = mat.length;
 
    // Function Call
    System.out.println(maxDiagonalSum(mat, N));
}
}
 
// This code is contributed by math_lover

# Python3 program for the above approach
 
# Function to return maximum diagonal
# sum that are parallel to main diagonal
def maxDiagonalSum(arr, N):
     
    # Initialize maxSum
    maxSum = 0
 
    # Traverse through the columns
    for i in range(N):
         
        # Initialize r and c
        row = 0
        col = i
 
        # Diagonal sums
        sum1 = 0
        sum2 = 0
         
        while col < N and row < N:
            sum1 += arr[row][col]
            sum2 += arr[col][row]
            row += 1
            col += 1
 
        # Update maxSum with
        # the maximum sum
        maxSum = max([ sum1, maxSum, sum2])
 
    # Return the maxSum
    return maxSum
 
# Driver Code
if __name__ == '__main__':
     
    # Given matrix mat[][]
    mat = [ [ 1, 2, 5, 7 ],
            [ 2, 6, 7, 3 ],
            [ 12, 3, 2, 4 ],
            [ 3, 6, 9, 4 ] ]
 
    N = len(mat)
 
    # Function Call
    print(maxDiagonalSum(mat, N))
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
class GFG{
   
// Function to return maximum
// diagonal sum that are parallel
// to main diagonal
static int maxDiagonalSum(int [,]arr,
                          int N)
{   
  // Initialize maxSum
  int maxSum = 0;
 
  // Traverse through the
  // columns
  for(int i = 0; i < N; i++)
  {
    // Initialize r and c
    int row = 0, col = i;
 
    // Diagonal sums
    int sum1 = 0, sum2 = 0;
    while (col < N && row < N)
    {
      sum1 += arr[row,col];
      sum2 += arr[col,row];
      row++;
      col++;
    }
 
    // Update maxSum with
    // the maximum sum
    maxSum = Math.Max(maxSum,
             Math.Max(sum1,
                      sum2));
  }
 
  // Return the maxSum
  return maxSum;
}
 
// Driver code
public static void Main(String[] args)
{   
  // Given matrix [,]mat
  int [,]mat = {{1, 2, 5, 7},
                {2, 6, 7, 3},
                {12, 3, 2, 4},
                {3, 6, 9, 4}};
  int N = mat.GetLength(0);
 
  // Function Call
  Console.WriteLine(maxDiagonalSum(mat, N));
}
}
 
// This code is contributed by gauravrajput1

<script>
// javascript program for the above approach
 
// Function to return maximum diagonal
// sum that are parallel to main diagonal
function maxDiagonalSum( arr,  N)
{
    // Initialize maxSum
    let maxSum = 0;
 
    // Traverse through the columns
    for (let i = 0; i < N; i++) {
 
        // Initialize r and c
        let row = 0, col = i;
 
        // Diagonal sums
        let sum1 = 0, sum2 = 0;
        while (col < N && row < N) {
            sum1 += arr[row][col];
            sum2 += arr[col][row];
            row++;
            col++;
        }
 
        // Update maxSum with
        // the maximum sum
        maxSum = Math.max(Math.max(sum1, maxSum), sum2 );
    }
 
    // Return the maxSum
    return maxSum;
}
 
// Driver Code
 
    // Given matrix mat[][]
    let mat
        = [[ 1, 2, 5, 7 ],
            [ 2, 6, 7, 3 ],
            [ 12, 3, 2, 4 ],
            [ 3, 6, 9, 4 ]];
    let N = mat[0].length;
 
    // Function Call
     document.write(maxDiagonalSum(mat, N));
 
// This code is contributed by todaysgaurav
</script>

18

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N ² )