Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск максимальной суммы в векторе 
:(
    Опции темы
MFSham
Дата 3.12.2005, 04:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 220
Регистрация: 28.8.2005
Где: Беларусь, Гродно

Репутация: нет
Всего: 3
Дан некоторый вектор, который может состоять как из положительных, так и отрицательных чисел. Найти в векторе непрерывную последовательность, которая образует максимальную сумму элементов, при этом каждый элемент просматривается ровно один раз.
Например :
-5 6 7 -2 1 8 9 -9 1 - данный вектор
1 8 9 - подпоследовательность с максимальной суммой
Подскажите пожалуйста алгоритм, а то че-то не получается.
--------------------
Без ветра трава неподвижна. Без программ компьютеры бесполезны.
PM MAIL   Вверх
amium
Дата 3.12.2005, 14:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 2.12.2005

Репутация: нет
Всего: нет
Код


#define N 10

const int n=3;

int v[N];
int sum=0, sum1=0,sum2=0;


int f=v[0];

int j;
for(j=0;j<n:j++){
  sum1+=v[j];
}

for(int i=1;i<N;i++){
  sum2 = sum1;
  f=v[i];
  sum1+=v[i+n-1];
  sum1-=f;
  sum=max(sum1,sum2);
}



Наверно так...
PM MAIL   Вверх
lovermann
Дата 3.12.2005, 23:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 285
Регистрация: 28.12.2004
Где: Прага

Репутация: нет
Всего: 8
amium, а кто сказал, что элементов должно быть 3? По заданию, их может быть сколько угодно. Или я неправильно понял твой код?
PM WWW ICQ   Вверх
amium
Дата 4.12.2005, 00:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 2.12.2005

Репутация: нет
Всего: нет
N и n можно менять по желанию. n также может не быть константой.
PM MAIL   Вверх
LSD
Дата 4.12.2005, 01:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538
Цитата(MFSham @ 3.12.2005, 04:45)
Например :
-5 6 7 -2 1 8 9 -9 1 - данный вектор
1 8 9 - подпоследовательность с максимальной суммой

У 6 7 -2 1 8 9 - сумма больше, или эта последовательность не подходит?


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
amium
Дата 4.12.2005, 18:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 2.12.2005

Репутация: нет
Всего: нет
Я думаю, что не подходит. Надо выбрать один размер для всех подпоследовательностей, в данном случае 3.
PM MAIL   Вверх
LSD
Дата 4.12.2005, 18:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538
Цитата(amium @ 4.12.2005, 18:41)
Надо выбрать один размер для всех подпоследовательностей, в данном случае 3.

В условии такого не было.


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Void
Дата 4.12.2005, 19:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


λcat.lolcat
****


Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 3
Всего: 173
Код
std::vector<int> v;
...
int s = v.front(), max_s = s, first = 0, last = 0;
for (int i = 0; i < v.size(); ++i) {
    s += v[i];
    if (s < 0 && (i < v.size() - 1 && v[i + 1] >= 0)) {
        first = i + 1;
        s = 0;
    }
    if (s >= max_s) {
        max_s = s;
        last = i;
    }
}

first, last - индексы первого и последнего элемента подпоследовательности с максимальной суммой, соответственно.

P.S. На архиэлементарную задачку убил полчаса. Плохо...

P.P.S. Обнаружил баг - не работает на последовательностях из одних отрицательных чисел. Думаю дальше...

Это сообщение отредактировал(а) Void - 4.12.2005, 19:55


--------------------
“Coming back to where you started is not the same as never leaving.” — Terry Pratchett
PM MAIL WWW GTalk   Вверх
Dov
Дата 4.12.2005, 20:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88
Цитата(Void @ 4.12.2005, 19:36)
std::vector<int> v;
...
int s = v.front(), max_s = s, first = 0, last = 0;
for (int i = 0; i < v.size(); ++i) {
    s += v[i];
    if (s < 0 && (i < v.size() - 1 && v[i + 1] >= 0)) {
        first = i + 1;
        s = 0;
    }
    if (s >= max_s) {
        max_s = s;
        last = i;
    }
}


Гы, плагиат. Void, ты зачем мой алгоритм скоммуниздил? Вот отседова. smile smile


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Dov
Дата 4.12.2005, 20:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88
Цитата(Void @ 4.12.2005, 19:36)
P.P.S. Обнаружил баг - не работает на последовательностях из одних отрицательных чисел. Думаю дальше...

И не должен работать, имхо. Потому как максимальной суммой одних отрицательных чисел является самое большое отрицательное число, и что бы его узнать не нужен алгоритм

Это сообщение отредактировал(а) Dov - 4.12.2005, 20:39


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Void
Дата 4.12.2005, 20:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


λcat.lolcat
****


Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 3
Всего: 173
Цитата(Dov @ 4.12.2005, 22:38)
И не должен работать, имхо. Потому как максимальной суммой одних отрицательных чисел является самое большое отрицательное число, и что бы его узнать не нужен алгоритм

Ну вот так работает же:
Код

std::vector<int> v;
...
int s = v.front(), max_s = s, first = 0, last = 0;
for (int i = 1; i < v.size(); ++i) {
    if (s < 0 && v[i] >= max_s) {
        first = i;
        s = v[i];
    } else
        s += v[i];
    if (s >= max_s) {
        max_s = s;
        last = i;
    }
}

smile


--------------------
“Coming back to where you started is not the same as never leaving.” — Terry Pratchett
PM MAIL WWW GTalk   Вверх
amium
Дата 4.12.2005, 21:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 2.12.2005

Репутация: нет
Всего: нет
Цитата(Void @ 4.12.2005, 19:36)
std::vector<int> v;
...
int s = v.front(), max_s = s, first = 0, last = 0;
for (int i = 0; i < v.size(); ++i) {
    s += v[i];
    if (s < 0 && (i < v.size() - 1 && v[i + 1] >= 0)) {
        first = i + 1;
        s = 0;
    }
    if (s >= max_s) {
        max_s = s;
        last = i;
    }
}



Но такой алгоритм не может работать с подпоследовательностями фиксированной длины. А зачем он тогда вообще нужен? - он всегда будет находить подпдследовательность от одного большого отрицательного числа до другого!
PM MAIL   Вверх
Void
Дата 4.12.2005, 21:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


λcat.lolcat
****


Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 3
Всего: 173
Цитата(amium @ 4.12.2005, 23:01)
Но такой алгоритм не может работать с подпоследовательностями фиксированной длины. А зачем он тогда вообще нужен? - он всегда будет находить подпдследовательность от одного большого отрицательного числа до другого!

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


--------------------
“Coming back to where you started is not the same as never leaving.” — Terry Pratchett
PM MAIL WWW GTalk   Вверх
Dov
Дата 4.12.2005, 21:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: нет
Всего: 88
Цитата(amium @ 4.12.2005, 21:01)
Но такой алгоритм не может работать с подпоследовательностями фиксированной длины. А зачем он тогда вообще нужен? - он всегда будет находить подпдследовательность от одного большого отрицательного числа до другого!


Цитата(MFSham @ 3.12.2005, 04:45)
Найти в векторе непрерывную последовательность, которая образует максимальную сумму элементов


amium, Где сказано, что алгоритм должен работать с подпоследовательностями фиксированной длины?




--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
LSD
Дата 4.12.2005, 21:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538
Void на таком [-5, 6, 7, -1000, 1, 8, 9, -9, 1] векторе твой алгоритм выдаст max_s = 13, first = 1, last = 2.


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0566 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.