JA3-Task-1-Sequence

Dimitar1236 2 Точки

JA3-Task-1-Sequence

Здравейте, разгледах ресурсите, които бяхте пуснали в дискусията, но не успях да намеря решение. Пробвах да реша задачата със Stack. Eто това, което съм направил досега.

#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;

int main()
{
   int i = 0, n;
   do
   {
       cin >> n;
   } while (!(n > 0 && n <= 1000));
   vector<int> input;
   stack<int> result;
   for (size_t i = 0; i < n; i++)
   {
       int element;
       cin >> element;
       input.push_back(element);
   }
   while (1)
   {
       if (input[i] < input[i + 1])
       {
           result.push(input[i]);
           //result.push(input[i + 1]);
           break;
       }
       else
           i++;
   }
   for (size_t j = i+1; j < n; j++)
   {
       if (input[j] > result.top())
           result.push(input[j]);
   }
   cout << result.size();
}

Тагове:

26/01/2021 13:23:49 C++ Fundamentals

Виж всички отговори

MartinBG 4803 Точки

Това е популярен проблем, за който има много информация в мрежата.

Разгледайте предложените решения от линковете по-горе - има и обяснения към тях.

Ето едно решение oт мен:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using Numbers = std::vector<int>;

Numbers parseNumbersFromStream(std::istream& in);

size_t getLongestIncreasingSubsequenceLength(Numbers const& numbers);

int main() {
  std::istream& in = std::cin;
  std::ostream& out = std::cout;

  Numbers numbers = parseNumbersFromStream(in);
  size_t lis = getLongestIncreasingSubsequenceLength(numbers);

  out << lis;

  return 0;
}

size_t getLongestIncreasingSubsequenceLength(Numbers const& numbers) {
  auto lis = Numbers(numbers.size());

  for (size_t i = 0; i < numbers.size(); i++) {
    lis[i] = 1;
    for (size_t j = 0; j < i; j++) {
      if (numbers[i] > numbers[j] && lis[i] < lis[j] + 1) {
        lis[i] = lis[j] + 1;
      }
    }
  }

  return *std::max_element(lis.cbegin(), lis.cend());
}

std::vector<int> parseNumbersFromStream(std::istream& in) {
  size_t size;
  in >> size;
  Numbers numbers(size);

  std::copy_n(std::istream_iterator<int>(in), size, numbers.begin());

  return numbers;
}

26/01/2021 22:12:39

Dimitar1236 2 Точки

Благодаря, ще го разгледам. Има ли как да ми представиш по-опростено решение, защото предполагам, че използваш похвати от advanced, а все още съм на Fundamentals.

Благодаря предварително!

26/01/2021 23:45:23

MartinBG 4803 Точки

Не се сещам какво да опростя по решението, което съм дал. Може би синтаксиса е различен от това, което е показвано в курса.

Разгледайте и решенията от линковете по-горе - например това.

27/01/2021 09:40:21

Виж всички отговори