Cod sursa(job #2294635)

Utilizator Tux2NicolaeTelechi Nicolae Tux2Nicolae Data 2 decembrie 2018 17:10:12
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
/**
 * Advent of code 2018
 * @author : Nicolae Telechi
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>

using namespace std;

//----------------------------------------------------------------------------


int main()
{
  ifstream in("ssm.in");
  ofstream out("ssm.out");

  vector<int> ret;

  int n = 0;
  while (in >> n)
    ret.push_back(n);

  // reserve +1 for a dummy element 0 witch will make our live easier, this will make
  // begin and end to point on the correct positions
  vector<int> sums;
  sums.reserve(ret.size() + 1);
  sums.push_back(0);

  std::partial_sum(ret.begin(), ret.end(),
    back_inserter(sums));

  int smax = std::numeric_limits<int>::min();
  int smaxbegin = 0, smaxend = 0;

  for (int beg = 0, end = 1; end < sums.size(); ++end)
  {
    if (sums[end] - sums[beg] > smax)
    {
      smax = sums[end] - sums[beg];
      smaxbegin = beg;
      smaxend = end;
    }

    // longest or shortest <=
    if (sums[end] < sums[beg])
      beg = end;
  }

  out << smax << " " << smaxbegin + 1 << "" << smaxend;
  return 0;
}