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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Марина4444
Сообщений: n/a
#1

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

15.02.2014, 16:51. Просмотров 432. Ответов 1
Метки нет (Все метки)

Здравствуйте. Мне попалась следующая задачка:
Имеется массив чисел. В нём могут находиться как отрицательные, так и положительные элементы. Его длина - n.

Необходимо найти наибольший подмассив этого массива. То есть, последовательность чисел с наибольшей суммой. И вывести номера крайних элементов.

Например:
Массив содержит: -1, 2, 6, 7, -5, 12, -1, -11, -5, 1.
Наибольшим подмассивом будет являться последовательность от второго элемента до шестого элемента.
2 + 6 + 7 + (-5) +12 = 22, где "2" - второй элемент, а "12" - шестой.

Я решила данную задачу следующим образом:

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
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
  {
  int L, R, Lmax, Rmax, n=10, i, sum=0, maxsum=0;
  int a[10] = { -1, 2, 6, 7, -5, 12, -1, -11, -5, 1 };
  for(L=0; L<n; L++)
    for(R=L; R<n; R++)
      {
      for(i=L; i<R; i++)
        sum = sum + a[i];
      if(sum > maxsum)
        {
        maxsum = sum;
        Lmax = L;
        Rmax = R;
        }
      sum = 0;
      }
  cout << maxsum << " " << Lmax+1 << " " << Rmax;
  getch();
  return;
  }
А какие ещё есть интересные алгоритмы её решения?
Спасибо ^^
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2014, 16:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти наибольший подмассив заданного массива (C++):

Найти наибольший простой множитель заданного числа - C++
Простые множители 13195 - 5, 7, 13 и 29. Каким является наибольший простой множитель заданного числа N? Входные данные: Первая...

Подмассив массива - C++
Ребят, помогите с теорией. Решаю очередную задачку на сайте ********. Что такое &quot;Подмассив массив&quot;. Не мог бы кто-нибудь конкретно на...

Что-то не хочет пахать :( | Даны два целочисленных массива К(m) и L(n). Найти наибольший элемент массива K, не имеющий себе равных в массиве L. - C++
Даны два целочисленных массива К(m) и L(n). Найти наибольший элемент массива K, не имеющий себе равных в массиве L. #include...

Найти наибольший элемент массива - C++
3. Найти наибольший элемент массива

Найти наибольший элемент массива - C++
Дан целочисленный массив В. Найти наибольший элемент массива и сообщить его расположение относительно левой диагонали.

Найти наибольший элемент массива - C++
Помогите пожалуйста решить задачу Заранее благодарю

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
16.02.2014, 00:03 #2
Можно воспользоваться следующим алгоритмом:
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).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.02.2014, 00:03
Привет! Вот еще темы с ответами:

Найти наибольший элемент массива - C++
Данный целочисленный массив В. Найти наибольший элемент массива.

Найти наибольший по модулю элемент массива - C++
2. Найти наибольший по модулю элемент

Найти наибольший элемент массива A отсутствующий в массиве B - C++
Даны два массива натуральных чисел A ( m ) и B ( n ) . Найти наибольший элемент в массиве A , которого нет в массиве B.

Найти наибольший и наименьший элементы вещественного массива - C++
Найти наибольший и наименьший элементы вещественного массива. Если таких элементов несколько, определить сколько их. Создать функции для...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru