inquis,
задача 2 наполовину решена где-то в c++'ных форумах, пошарь там.
| Код | #include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
#include <iostream>
#include <iterator>
/*
Задача 1.
Последовательность из десяти целых чисел (как положительных, так и отрицательных)
представлена в виде одномерного массива. Найти и вывести на экран подпоследовательность
подряд идущих чисел, сумма которых максимальна.
Например, для последовательности : 1 -8 3 2 -1 4 -6 2 1 -5
ответом будет следующая подпоследовательность: 3 2 -1 4
*/
template <typename _InIt>
std::pair<_InIt, _InIt> find_sequence(_InIt begin, _InIt end)
{
std::pair<_InIt, _InIt> res;
typedef typename std::iterator_traits<_InIt>::value_type value_type;
value_type maxElem = std::numeric_limits<value_type>::min();
// В общем обычный, тупой перебор
for ( ; begin != end; ++begin)
for (_InIt it = begin; it != end; ++it)
{
value_type sum = std::accumulate(begin, it+1, value_type());
if (sum > maxElem)
maxElem = sum, res = std::make_pair(begin, it+1);
}
return (res);
} |
3.
| Код | #include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
#include <iostream>
#include <iterator>
/*
В заданной последовательности чисел длиной n (n≤100)
определить длину самой большой упорядоченной по возрастанию
подпоследовательности соседних элементов.
*/
template <typename _InIt>
typename std::iterator_traits<_InIt>::difference_type
sequence_length(_InIt begin, _InIt end)
{
typedef typename std::iterator_traits<_InIt>::value_type value_type;
typename std::iterator_traits<_InIt>::difference_type count = 0;
for ( ; begin != end; ++begin)
for (_InIt it = begin + 1; it != end; ++it)
{
// Пытаемся найти возрастающую последовательность
if (std::adjacent_find(begin, it + 1, std::greater<value_type>()) != it + 1)
break;
// Последовательность найдена, обновим данные о длине
count = std::max(count, std::distance(begin, it + 1));
}
return (count);
} |
использование:
| Код | const size_t N = ...
int arr[N] = {...};
std::pair<int*, int*> res = find_sequence(arr, arr + N);
size_t cnt = sequence_length(arr, arr + N); |
|
