Maximice la suma atravesando en diagonal desde cada celda de una Array dada

Dada una array cuadrada 2D arr[][] de dimensiones N x N , la tarea es encontrar la suma máxima de la ruta moviéndose en diagonal desde cualquier celda y cada celda debe visitarse solo una vez, es decir, desde la celda (i, j) , un jugador puede moverse a la celda (i + 1, j + 1) .

Ejemplos:

Entrada: arr[][] = {{ 1, 2, 3}, {3, 5, 10}, {1 3 5}} 
Salida: 12
Explicación:
Suma de celdas (1, 1), (2, 2) y (3, 3) es 11.  
La suma de las celdas (1, 2), (2, 3) y (1, 3) es 3. 
La suma de las celdas (2, 1) y (3, 2) es 6de
la celda (3, 1) es 1.
La suma máxima posible es 12.

Entrada: arr[][] = {{1, 1, 1}, {1 1 1}, {1 1 1}} 
Salida: 3

Enfoque: Para resolver este problema, la idea es atravesar la array en diagonal para los elementos de la primera fila y la columna y sumar sus elementos diagonales dentro del rango de la array. 
Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos max con 0 .
2. Elija cada celda (i, j) de la primera fila y de la primera columna.
3. Ahora, de cada celda, encuentre la suma diagonal a partir de esa celda incrementando i y j en 1 , digamos sum .
4. Luego, actualice max como max(max, sum) .
5. Después de atravesar, imprima max como la respuesta requerida.

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 find the maximum sum
int MaximumSum(vector<vector<int> >& arr, int n)
{
 
    int ans = 0;
 
    // Loop to traverse through the
    // upper triangular matrix and
    // update the maximum sum to ans
    for (int i = 0; i < n; i++) {
        int x = 0, y = i, sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
 
    // Traverse through the
    // lower triangular matrix
    for (int i = 1; i < n; i++) {
 
        int x = i, y = 0, sum = 0;
 
        for (int j = i; j < n; j++) {
 
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
 
    return ans;
}
 
// Driver Code
int main()
{
 
    // Given matrix
    vector<vector<int> > arr;
    arr = { { 1, 2, 3 },
            { 3, 5, 10 },
            { 1, 3, 5 } };
 
    // Given dimension
    int n = arr.size();
 
    cout << MaximumSum(arr, n);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the maximum sum
static int MaximumSum(int [][]arr, int n)
{
 
    int ans = 0;
 
    // Loop to traverse through the
    // upper triangular matrix and
    // update the maximum sum to ans
    for (int i = 0; i < n; i++)
    {
        int x = 0, y = i, sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
 
    // Traverse through the
    // lower triangular matrix
    for (int i = 1; i < n; i++)
    {
        int x = i, y = 0, sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given matrix
    int [][]arr = { { 1, 2, 3 },
            { 3, 5, 10 },
            { 1, 3, 5 } };
 
    // Given dimension
    int n = arr.length;
    System.out.print(MaximumSum(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
 
# Function to find the maximum sum
def MaximumSum(arr, n):
    ans = 0;
 
    # Loop to traverse through the
    # upper triangular matrix and
    # update the maximum sum to ans
    for i in range(n):
        x, y, sum = 0, i, 0
        for j in range(i, n):
            sum, x, y =sum + arr[x][y], x + 1, y + 1
        if (sum > ans):
            ans = sum
 
    # Traverse through the
    # lower triangular matrix
    for i in range(1, n):
 
        x, y, sum = i, 0, 0
 
        for j in range(i, n):
 
            sum, x, y =sum + arr[x][y], x + 1, y + 1
        if (sum > ans):
            ans = sum
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    # Given matrix
    arr = [ [ 1, 2, 3],
            [ 3, 5, 10],
            [ 1, 3, 5 ]]
 
    # Given dimension
    n = len(arr)
    print (MaximumSum(arr, n))
 
    # This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG{
 
  // Function to find the maximum sum
  static int MaximumSum(int [,]arr, int n)
  {
    int ans = 0;
 
    // Loop to traverse through the
    // upper triangular matrix and
    // update the maximum sum to ans
    for (int i = 0; i < n; i++)
    {
      int x = 0, y = i, sum = 0;
      for (int j = i; j < n; j++)
      {
        sum += arr[x++, y++];
      }
      if (sum > ans)
        ans = sum;
    }
 
    // Traverse through the
    // lower triangular matrix
    for (int i = 1; i < n; i++)
    {
      int x = i, y = 0, sum = 0;
      for (int j = i; j < n; j++)
      {
        sum += arr[x++, y++];
      }
      if (sum > ans)
        ans = sum;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Given matrix
    int [,]arr = { { 1, 2, 3 },
                  { 3, 5, 10 },
                  { 1, 3, 5 } };
 
    // Given dimension
    int n = arr.GetLength(0);
    Console.Write(MaximumSum(arr, n));
  }
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program of the above approach
 
// Function to find the maximum sum
function MaximumSum(arr, n)
{
  
    let ans = 0;
  
    // Loop to traverse through the
    // upper triangular matrix and
    // update the maximum sum to ans
    for (let i = 0; i < n; i++)
    {
        let x = 0, y = i, sum = 0;
        for (let j = i; j < n; j++)
        {
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
  
    // Traverse through the
    // lower triangular matrix
    for (let i = 1; i < n; i++)
    {
        let x = i, y = 0, sum = 0;
        for (let j = i; j < n; j++)
        {
            sum += arr[x++][y++];
        }
        if (sum > ans)
            ans = sum;
    }
    return ans;
}
 
    // Driver Code
     
    // Given matrix
    let arr = [[ 1, 2, 3 ],
            [ 3, 5, 10 ],
            [ 1, 3, 5 ]];
  
    // Given dimension
    let n = arr.length;
    document.write(MaximumSum(arr, n));
  
</script>

12

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