Envío 2234

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 !!!

  // O(n^2)
  for (int i = 0; i < n; i++) {  // O(n)
    long long sum = 0;
    for (int j = i; j < n; j++) { // O(n)
      // Aquí tenemos un posible subarreglo.
      // Encontrar su suma y ver si es la mejor que hemos visto
      // hasta ahora.
      sum += a[j];

      best = max(best, sum);
    }
  }

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