Cod sursa(job #2233503)

Utilizator rares.amarandeiRares Amarandei rares.amarandei Data 23 august 2018 15:12:22
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb

#include <stdint.h>
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <memory>
#include <algorithm>
#include <deque>
#include <iterator>
#include <numeric>
#include <assert.h>
#include <limits>
#include <queue>
#include <fstream>

using namespace std;

vector<int> runAlgorithm(const vector<int> input)
{
 vector<vector<int>> outputCandidates;
    outputCandidates.push_back(vector<int>{input[0]});
    for (int i = 1; i < input.size(); ++i)
    {
      vector<vector<int>> processedCandidates;
      bool candidatesUpdated = false;
      for (auto& candidate : outputCandidates) 
      {
        if (candidate.back() < input[i]) 
        {
          candidate.push_back(input[i]);
          candidatesUpdated = true;
        }
        else
        {
          vector<int> temp = candidate;
          while (!temp.empty() && temp.back() >= input[i]) {
            temp.pop_back();
          }
          temp.push_back(input[i]);
          processedCandidates.push_back(temp);
        }
      }
      outputCandidates.insert(outputCandidates.end(), processedCandidates.begin(), processedCandidates.end());
    }

    int maxSize = 0;
    vector<int> output;
    for (auto candidate : outputCandidates) 
    {
      if(maxSize < candidate.size())
      {
        maxSize = candidate.size();
        output = candidate;
      }
    }

    return output;
}

int main() {
  ifstream f("scmax.in");
  ofstream g("scmax.out");
  vector<int> input;
  vector<int> output;
  int n = 0;
  f >> n;
  int x = 0;
  for (int i = 0; i<n; i++)
  {
    f >> x;
    input.push_back(x);
  }
  output = runAlgorithm(input);
  g << output.size() << '\n';
  for (auto it = output.begin(); it != output.end(); ++it)
  {
    g << *it << ' ';
  }
  return 0;
}