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

Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Как представить натуральное число в виде произведения двух простых чисел http://www.cyberforum.ru/cpp-beginners/thread1306371.html
Нашел что то похожее только, там 3 простых числа, и проблема в том что код написан на Paskalе, если можете объяснить или написать код для Borland C++, буду очень признателен Код с 3мя простыми числами: uses crt; function Prost(n:longint):boolean; var i:longint; f:boolean; begin if i<2 then f:=false else begin
C++ Дан текстовый файл с неизвестным количеством вещественных чисел Дан текстовый файл с неизвестным количеством вещественных чисел. Написать функцию для определения есть ли среди них число у которого сумма цифр целой и дробной части равны http://www.cyberforum.ru/cpp-beginners/thread1306370.html
Дана матрица размерностью 6х6 C++
Дана матрица размерностью 6х6.В этой матрице найти минимальный элемент,лежащий ниже побочной диагонали, и заменить его на 0
Задача на двумерные массивы C++
Заменить элементы главной диагонали матрицы целых чисел 5х5 суммами элементов столбцов. void __fastcall TForm1::Button1Click(TObject *Sender) {int a,i,j; int S; for(i=0;i<5;i++) for(j=0;j<5;j++) a=StrToFloat(StringGrid1->Cells); for(j=0;j<5;j++) S=0; for(i=0;i<5;i++)
C++ Конечная сумма http://www.cyberforum.ru/cpp-beginners/thread1306364.html
Для заданного к и ч посчитать следующее выражение \sum \frac{{-1}^{n-1}*{x}^{n}} {2n!}
C++ Определить есть ли в файле число у которого сумма цифр целой и дробной части равны Дан текстовый файл с неизвестным количеством вещественных чисел. Написать функцию для определения есть ли среди них число у которого сумма цифр целой и дробной части равны подробнее

Показать сообщение отдельно
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2908 / 1444 / 397
Регистрация: 18.10.2014
Сообщений: 2,662
20.11.2014, 22:20     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Подкиньте идею как сделать за O (n).
Если мысленно заменить 0 на -1, то задача превратится в поиск самой длинной подпоследовательности с нулевой суммой.

1. Пусть у нас есть A[n] с элементами -1 и +1
2. Берем еще один массив S[n]. Заполняем его по правилу S[i] = сумма всех элементов A в диапазоне [0..i].
3. Если в S есть нуль в позиции i, то A[0..i] имеет нулевую сумму
4. Если для i < j выполняется S[i] == S[j], то A[i..j] имеет нулевую сумму

То есть задача сводится к проходу по S и эффективному определению, встречалось ли уже такое значение ранее. Учитывая, что значения S по модулю не превосходят n задача решается элементарно.
 
Текущее время: 23:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru