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

Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной - C++

Восстановить пароль Регистрация
 
TF
0 / 0 / 0
Регистрация: 20.03.2013
Сообщений: 87
31.10.2013, 22:21     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #1
массив из случайных целых чисел от -1000 до 1000. задача найти непрерывную часть этого массива чтобы сумма элементов была максимальной
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2013, 22:21     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Посмотрите здесь:

C++ Найти ошибку(сумма элементов массива)
C++ Найти в диапазоне от 10 до 99 такие 3 последовательные числа, чтобы сумма их цифр была равна 15
C++ Рекурсия: найти сумму элементов массива
Найти количество элементов массива вещественных чисел, дробная часть которых равна 0,5 C++
C++ В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IchimaruGin
59 / 59 / 22
Регистрация: 14.07.2013
Сообщений: 282
Завершенные тесты: 1
01.11.2013, 00:51     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #2
Цитата Сообщение от TF Посмотреть сообщение
чтобы сумма элементов была максимальной
и как понять ваше условие? по сравнению с чем сума скольких елементов должна быть максимальной? В каком смысле неприрывную?
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
01.11.2013, 10:55     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #3
IchimaruGin, я думаю так:
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
#include <iostream>
using namespace std;
 
int main()
{
const int n = abs(-1000) + 1 + 1000;
int arr[n];
 
for( int i=0; i<n; i++ )
  arr[i] = rand();
 
int currSumm,
    numBegin=arr[0],
    numEnd=arr[0],
    summ=0;
 
for( int begin=0; begin<n; begin++ )
  {
  currSumm = 0;
  for(int end=begin; end<n; end++ )
    {
    currSumm += arr[end];
    if( currSumm > summ )
      {
      summ = currSumm;
      numBegin = begin; // Хрен его знает зачем
      numEnd = end;     //
      }
    }
  }
cout << summ;
cin.ignore();
        return 0;
}
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
01.11.2013, 11:35     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #4
Цитата Сообщение от SatanaXIII Посмотреть сообщение
numBegin=arr[0],
* * numEnd=arr[0],
Наверное не arr[0], а просто -1?

Надеюсь, что эту задачу дали как пример того, когда не надо использовать рекурсию. А то у нее будет просто ужасная алгоритмическая сложность - из-за постоянных перевычислений одного и того же.

SatanaXIII тоже предложил не самый лучший алгоритм - у него O(n*n). А задача решается с помощью динамического программирования - один раз проходим циклом по массиву, на каждой позиции находя максимальный подмассив, кончающийся на этой позиции. Тогда сложность - О(n).
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
01.11.2013, 12:03     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #5
Цитата Сообщение от ct0r Посмотреть сообщение
Наверное не arr[0], а просто -1?
Почему?

Цитата Сообщение от ct0r Посмотреть сообщение
решается с помощью динамического программирования - один раз проходим циклом по массиву, на каждой позиции находя максимальный подмассив, кончающийся на этой позиции. Тогда сложность - О(n).
Зато проигрыш в памяти.
Потом все равно потребуется еще один проход, но уже по созданному массиву.
ct0r
C++/Haskell
 Аватар для ct0r
1549 / 568 / 39
Регистрация: 19.08.2012
Сообщений: 1,174
Завершенные тесты: 1
01.11.2013, 12:51     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #6
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Почему?
Ну потому что иначе странно - ты инициализируешь по сути случайными значениями массива, а потом пихаешь туда индексы.

Цитата Сообщение от SatanaXIII Посмотреть сообщение
Зато проигрыш в памяти.
Потом все равно потребуется еще один проход, но уже по созданному массиву.
Там нету проигрыша в памяти, потому что мы ничего не создаем:
http://en.wikipedia.org/wiki/Maximum_subarray_problem
Кстати, даже если бы понадобился еще один проход, то это все равно О(n), а не O(n*n).
И даже если бы использовалась дополнительная память, то производительность все равно в 90% случаев важнее.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
01.11.2013, 13:18     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #7
Цитата Сообщение от ct0r Посмотреть сообщение
Ну потому что иначе странно - ты инициализируешь по сути случайными значениями массива, а потом пихаешь туда индексы.
Действительно.
Только не -1, а 0. n то у нас больше чем ноль - защита не нужна.

Цитата Сообщение от ct0r Посмотреть сообщение
Maximum_subarray_problem
Спасибо. Почитал.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Еще ссылки по теме:

C++ Отсортировать строки массива так, чтобы первой шла строка, сумма элементов которой была меньше, чем остальных
Рекурсия: найти количество отрицательных элементов массива C++
C++ Рекурсия: сумма массива

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

Или воспользуйтесь поиском по форуму:
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #8
Вот мой вариант решения задачи. Алгоритм - получение методом перебора всех под-последовательностей элементов с каждой позиции в массиве. Далее вычисление суммы элементов каждой из под-последовательностей, далее нахождение наибольшей суммы.
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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
#define N 10
 
int main(int argc, char* argv[])
{
    int A[N] = { 0 };
    for (int i = 0; i < N; i++)
    {
        A[i] = rand() % 2000 - 1000;
        printf("%d ",A[i]);
    }
 
    printf("\n\n");
 
    int max = 0, pos = 0, len = 0;
    for (int t = 0; t < N; t++)
    {
        int cnt = 0;
        while (cnt < N)
        {
            int k = t, sum = 0;
            while (k <= cnt) sum+=A[k++];
            if (sum > max) { max = sum; pos = t; len = cnt-pos+1; }
 
            cnt++;
        }
    }
 
    printf("sum = %d pos = %d len = %d\n",max,pos,len);
 
    _getch();
}
http://codepad.org/MKOuhrDx
Миниатюры
Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной  
Yandex
Объявления
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Ответ Создать тему
Опции темы

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