█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 3908

Problema 0xa6 - Submatriz de suma máxima en una matriz no muy grande

  • Autor: bryancalisto
  • Fecha: 2021-04-21 04:22:03 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#2
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#3
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#4
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#5
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#6
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#7
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#8
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#9
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#10
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#11
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#12
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#13
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#14
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#15
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#16
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#17
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
#18
Error de compilación
                      main.c:29:44: error: use of undeclared identifier 'INT_MIN'
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;
                                           ^
1 error generated.

                    
Puntos totales: 0 / 100

Código

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a,int b){
  return a > b? a: b;
}

// Para encontrar valor de la mayor suma de los subarrays de un array en O(n)
int kadane(int *arr, int len)
{
  int sumaMax = -10000;
  int sumaActual = 0;

  for (int i = 0; i < len; i++)
  {
    sumaActual = max(arr[i], arr[i] + sumaActual);
    if (sumaActual > sumaMax)
    {
      sumaMax = sumaActual;
    }
  }

  return sumaMax;
}

int main()
{
  int i, j, k, l, R, C, *matriz, sumaMax = INT_MIN, *tmp;

  // INPUT
  fscanf(stdin, "%d %d", &R, &C);
  matriz = (int *)malloc(sizeof(int) * R * C);

  for (i = 0; i < R; i++)
  {
    for (j = 0; j < C; j++)
    {
      fscanf(stdin, "%d", matriz + i * C + j);
    }
  }

  // ALGORITMO
  tmp = (int *)calloc(R * C, sizeof(int)); // matriz temporal

  for (i = 0; i < R; i++)
  {
    for (j = 0; j < C; j++)
    {
      if (j > 0)
      {
        *(tmp + i * C + j) = *(matriz + i * C + j) + *(tmp + i * C + j - 1);
      }
      else
      {
        *(tmp + i * C + j) = *(matriz + i * C + j);
      }
    }
  }

  int nums;
  for (i = 0; i < C; i++)
  {
    for (j = i; j < C; j++)
    {
      nums = 1;
      int *v = (int *)malloc(sizeof(int) * nums);
      for (k = 0; k < R; k++)
      {
        l = 0;
        if (i > 0)
        {
          l = *(tmp + k * C + j) - *(tmp + k * C + i - 1);
        }
        else
        {
          l = *(tmp + k * C + j);
        }

        v[nums - 1] = l;
        nums++;
        v = (int *)realloc(v, sizeof(int) * nums);
      }

      sumaMax = max(sumaMax, kadane(v, nums - 1));
      free(v);
    }
  }

  printf("%d\n", sumaMax);

  free(matriz);
  free(tmp);
  return 0;
}