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

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

Восстановить пароль Регистрация
 
Марина4444
Сообщений: n/a
15.02.2014, 16:51     Найти наибольший подмассив заданного массива #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++ Что-то не хочет пахать :( | Даны два целочисленных массива К(m) и L(n). Найти наибольший элемент массива K, не имеющий себе равных в массиве L.
Найти наибольший общий делитель всех элементов массива C++
Найти наибольший и наименьший элементы вещественного массива C++
C++ Найти наибольший элемент массива в каждой строке.
Подмассив массива C++
Найти наибольший элемент массива C++
C++ Двумерный массив. Найти подмассив, имеющий наибольшую сумму элементов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
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).
Yandex
Объявления
16.02.2014, 00:03     Найти наибольший подмассив заданного массива
Ответ Создать тему
Опции темы

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