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

Найти наибольший подмассив заданного массива - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Нахождение суммы элементов массива, найти ошибку в коде http://www.cyberforum.ru/cpp-beginners/thread1097243.html
#include <iostream> #include <time.h> using namespace std; void fm(int a, int count){ for (int i=0; i<count; i++) a=rand()%100; } void print(int a,int count){ for (int i=0; i<count; i++)
C++ Вывести имя и количество букв в фамилии. Вывести самое длинное слово Помогите сделать задачку: Вывести имя и количество букв в фамилии.Вывести самое длинное слово.На C++ http://www.cyberforum.ru/cpp-beginners/thread1097241.html
Добавление элемента в список с проверкой уникальности C++
Всем привет! И сразу же к сути - не могу разобраться с добавлением элемента в список, но так что бы он не повторялся и был на своему мести, например мы добавили 7, в список 1 3 5 6 9, результат 1 3 5 6 7 9! Вот код программы: //--------------------------------------------------------------------------- #include <clx.h> #include <iostream.h> #include <stdio.h> #include <conio.h> #include...
C++ Ссылка на двумерный массив
Здравствуйте. Объясните досконально это выражение: int (&ref1);
C++ Логарифмы и не объявленные идентификаторы - найти ошибку в коде http://www.cyberforum.ru/cpp-beginners/thread1097219.html
#include <iostream> #include <conio.h> #include <math.h> void main() { float x,y; // объявление переменных
C++ Установка wxWidgets3.0 в Code Blocks Привет, помогите пожалуйста установить wxWidgets3.0 в Code Blocks, а то сил уже никаких нету( как его туда запихать ? подробнее

Показать сообщение отдельно
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
16.02.2014, 00:03     Найти наибольший подмассив заданного массива
Можно воспользоваться следующим алгоритмом:
1) Для каждого элемента найти наибольшую подпоследовательность из всех подпоследовательностей, заканчивающихся на этом элементе.
2) выбрать из них максимальную - она будет наибольшей подпоследовательностью массива

Для элемента №0 такая подпоследовательность, очевидно, содержит только его самого.
Для любого другого элемента такая подпоследовательность содержит его самого и, возможно, наибольшую подпоследовательность предыдущего элемента.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n= 10;
int a[10] = { -1, 2, 6, 7, -5, 12, -1, -11, -5, 1 };
// отсюда начинается алгоритм поиска
int L = 0;
int Lmax = 0;
int Rmax = 0;
int sum = a[0];
int maxsum = a[0];
 
for (int i = 1; i < n; ++i)
{
    if (sum < 0) // если наибольшая подпоследовательность предыдущего элемента отрицательна, 
            // то ее не надо включать в наибольшую подпоследовательность текущего элемента
    {
        L = i;
        sum = a[i];
    }
    else
        sum += a[i];
 
    if (sum > maxsum)   // здесь выбираем максимальную подпоследовательность массива
    {
        Lmax = L;
        Rmax = i;
        maxsum = sum;
    }
}
Алгоритм имеет сложность http://www.cyberforum.ru/cgi-bin/latex.cgi?O(n).
 
Текущее время: 19:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru