Envío 2232

Problema 0x94 - Subarreglo de máxima suma

Autor: Mejibyte
Fecha: 2020-12-06 22:37:10 UTC (Hace más de 3 años)

Caso #	Resultado	Tiempo	Memoria
#1	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#2	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#3	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#4	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#5	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#6	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#7	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#8	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#9	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#10	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#11	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#12	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#13	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#14	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#15	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#16	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#17	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#18	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#19	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#20	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#21	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#22	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#23	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.
#24	Error de compilación main.c:1:10: fatal error: 'vector' file not found #include <vector> ^~~~~~~~ 1 error generated.

Puntos totales: 0 / 100

Código

#include <vector>
#include <iostream>
#include <limits>
using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  // Inicializar best en -infinito.
  // long long best = std::numeric_limits<long long>::min(); // Opción 1

  long long best = a[0]; // Esto asume que n >= 1 !!!

  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      // Aquí tenemos un posible subarreglo.
      // Encontrar su suma y ver si es la mejor que hemos visto
      // hasta ahora.
      // int: 16 bits
      // long: 32 bits
      // long long 64 bits
      // En Go: int16, int32, int64
      long long sum = 0; // 2^31 - 1 // signed vs unsigned int
      for (int k = i; k <= j; k++) {
        sum += a[k];
      }
      best = max(best, sum);
    }
  }

  cout << best << endl;
  return 0;
}