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

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

Восстановить пароль Регистрация
 
FreeMan108
 Аватар для FreeMan108
120 / 120 / 6
Регистрация: 04.03.2013
Сообщений: 368
20.11.2014, 21:36     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #1
Здравствуйте.
Задана последовательность из 0 и 1. Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.

Реализовал простым перебором за O (n2).
Подкиньте идею как сделать за O (n).
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2014, 21:36     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.
Посмотрите здесь:

Поиск самой длинной неубывающей подпоследовательности C++
C++ Подсчитать количество символов в самой длинной группе
C++ Определить длину самой длинной подстроки из подряд стоящих букв «е»
C++ Деревья С++ (функция, которая получает указатель на корень дерева и возвращает длину самой длинной ветки на дереве)
Определить длину самой длинной цепочки единиц в переменной unsigned long a; C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
20.11.2014, 22:18     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #2
Примерно вот так.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    char *str = "011011111000000111100110101011010";
    int tempMax = 1;
    int max = 0;
    char maxValue = *str;
    for (char *value = str, *endStr = str + strlen(str); value < endStr; ++value)
    {
        if (maxValue != *value)
        {
            maxValue = *value;
            max = max > tempMax ? max : tempMax;
            tempMax = 1;
        }
        else
        {
            tempMax++;
        }
    }
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2779 / 1425 / 393
Регистрация: 18.10.2014
Сообщений: 2,621
20.11.2014, 22:20     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от 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 задача решается элементарно.
FreeMan108
 Аватар для FreeMan108
120 / 120 / 6
Регистрация: 04.03.2013
Сообщений: 368
20.11.2014, 22:24  [ТС]     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #4
Цитата Сообщение от Nosey Посмотреть сообщение
Примерно вот так.
Не работает для "1100"
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2779 / 1425 / 393
Регистрация: 18.10.2014
Сообщений: 2,621
20.11.2014, 22:27     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #5
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
4. Если для i < j выполняется S[i] == S[j], то A[i..j] имеет нулевую сумму
Коррекция

4. Если для i < j выполняется S[i] == S[j], то A[i+1..j] имеет нулевую сумму

Если вообразить, что массив S имеет элемент S[-1] со значением 0, то пункт 3 сводится к пункту 4
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
20.11.2014, 22:27     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #6
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Не работает для "1100"
Да, я уже прочитал условие Там неверный алгоритм, я наибольшую непрерывную последовательность искал.
FreeMan108
 Аватар для FreeMan108
120 / 120 / 6
Регистрация: 04.03.2013
Сообщений: 368
20.11.2014, 22:38  [ТС]     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #7
TheCalligrapher,
1 и 2 понятно, но если у нас есть массив сумм, то надо найти такие i, j, что j - i = max и S[j] == S[i]. Как это сделать за O (n)?

Добавлено через 5 минут
Все! Кажись придумал! Создать вспомогательный массив bool, куда записывать встречалась ли такая сумма и изменять max если j - i > max.

Всем спасибо!
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
20.11.2014, 22:38     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #8
FreeMan108,

C++ (Qt)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#undef NDEBUG
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#endif
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y1 __y1
#define endl '\n'
#define sqr(x) (x) * (x)
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld pi = ld(3.1415926535897932384626433832795);
 
bool in(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}
 
inline int myrand()
{
    return rand() ^ (rand() << 15);
}
 
const int N = 1e6;
 
map<int, int> pos;
int a[N], pref[N];
int n;
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cout << setprecision(10) << fixed;
    cerr << setprecision(10) << fixed;
 
    srand(int(time(NULL)));
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        assert(a[i] == 0 || a[i] == 1);
        if(a[i] == 0)
            a[i] = -1;
        pref[i] = a[i] + (i > 0 ? pref[i - 1] : 0);
        pos[pref[i]] = max(pos[pref[i]], i);
    }
 
    int ans = 0, lf = -1, rg = -1;
 
    for(int l = 0; l < n; l++)
    {
        int need = (l > 0 ? pref[l - 1] : 0);
        if(pos.count(need) == 0)
            continue;
 
        int r = pos[need];
        if(r - l + 1 > ans)
        {
            ans = r - l + 1;
            lf = l, rg = r;
        }
    }
 
    cout << ans << endl;
    cout << lf << ' ' << rg << endl;
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2014, 23:09     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.
Еще ссылки по теме:

C++ Функция нахождения самой длинной неубывающей подпоследовательности
C++ Определить количество чисел в наиболее длинной подпоследовательности из нулей
Найти длину самой длинной последовательности подряд идущих нулевых элементов массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2779 / 1425 / 393
Регистрация: 18.10.2014
Сообщений: 2,621
20.11.2014, 23:09     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1. #9
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Создать вспомогательный массив bool,
Лучше не 'bоol', а массив индексов, по которому в первый раз была встречена такая сумма.

Цитата Сообщение от FreeMan108 Посмотреть сообщение
Как это сделать за O (n)?
Мой вариант (явные массивы A и S я не формирую, а просто вычисляю текущую сумму 's' на лету)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <iomanip>
#include <iterator>
using namespace std;
 
int main()
{
  const char SEQ[] = "011011111000000111100110101011010";
  const size_t N = sizeof(SEQ) - 1;
 
  size_t indices_mem[N * 2 - 1];
  for (size_t i = 0; i < N * 2 - 1; ++i)
    indices_mem[i] = -1;
 
  size_t *const indices = indices_mem + N - 1;
  indices[0] = -1;
 
  size_t max_length = 0, max_lo;
  int s = 0;
 
  for (size_t i = 0; i < N; ++i)
  {
    s += SEQ[i] == '0' ? -1 : +1;
 
    if (indices[s] == -1)
    {
      indices[s] = i;
      continue;
    }
 
    size_t length = i - indices[s];
    if (length > max_length)
    {
      max_length = length;
      max_lo = indices[s] + 1;
    }
  }
 
  if (max_length == 0)
    cout << "No such subsequence" << endl;
  else
  {
    cout << "Length = " << max_length << " [" << max_lo << ", " << max_lo + max_length - 1 << "]" << endl;
    copy(SEQ + max_lo, SEQ + max_lo + max_length, ostream_iterator<char>(cout));
    cout << endl;
  }
}
Добавлено через 11 минут
Цитата Сообщение от FreeMan108 Посмотреть сообщение
Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.
Вообще-то с формальной точки зрения термин "подпоследовательность" не требует того, чтобы ее элементы располагались рядом в исходной последовательности.

Но в данной задаче, по-видимому, имеется в виду непрерывная подпоследовательность. Иначе задача стала бы тривиальной.
Yandex
Объявления
20.11.2014, 23:09     Нужно найти длину самой длинной подпоследовательности, в которой равное количество 0 и 1.
Ответ Создать тему
Опции темы

Текущее время: 02:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru