Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Верхний и нижний регистр http://www.cyberforum.ru/cpp-beginners/thread994162.html
Напишите программу, которая читает клавиатурный ввод до символа @ и повторяет его, за исключением десятичных цифр, преобразуя каждую букву верхнего регистра в букву нижнего регистра и наоборот....
C++ Вычислить последовательность Не знаю почему, но программа отказывается выдавать что-либо, помогите найти ошибку. /*Для данного вещественного числа x и натурального n вычислить: c) sin x + sin(sin x ) + ... + sin ( sin (...... http://www.cyberforum.ru/cpp-beginners/thread994138.html
C++ Найти в одномерном массиве, состоящем из N целых чисел, количество простых элементов
Нужна помощь, буду очень благодарен) Общая постановка задания: Используя динамический массив и функции, найти количество простых чисел. И если можно, то к этому же заданию: преобразовать массив...
C++ Реализация одиночного наследования
Парни, выручайте! а) Создать иерархию классов датчик – абстрактный базовый класс и датчики температуры, влажности и скорости ветра. Для каждого класса определить свои единицы измерения и способ...
C++ Найти максимальное и минимальное значение между точками и вывести их вместе с точками http://www.cyberforum.ru/cpp-beginners/thread994098.html
Я уже весь гугл перерыл и всю голову выпотрошил.не получается. Нужно написать функцию для двух массивов х и у. Эти массивы задают координаты точек.Надо найти максимальное и минимальное значение между...
C++ Классы. Программирование алгоритмов с использованием конструктора, деструктора, friend - функции инициализации set() и функции вывода результатов prin Братаны, выручайте!:help: Общая постановка. Пользовательский класс Х должен содержать необходимые элементы-данные, которые создаются в динамической области памяти. * Конструктор для их создания... подробнее

Показать сообщение отдельно
ct0r
Игогошка!
1773 / 675 / 42
Регистрация: 19.08.2012
Сообщений: 1,287
Завершенные тесты: 1
01.11.2013, 11:35
Цитата Сообщение от SatanaXIII Посмотреть сообщение
numBegin=arr[0],
* * numEnd=arr[0],
Наверное не arr[0], а просто -1?

Надеюсь, что эту задачу дали как пример того, когда не надо использовать рекурсию. А то у нее будет просто ужасная алгоритмическая сложность - из-за постоянных перевычислений одного и того же.

SatanaXIII тоже предложил не самый лучший алгоритм - у него O(n*n). А задача решается с помощью динамического программирования - один раз проходим циклом по массиву, на каждой позиции находя максимальный подмассив, кончающийся на этой позиции. Тогда сложность - О(n).
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru