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

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

Войти
Регистрация
Восстановить пароль
 
Василицк
0 / 0 / 0
Регистрация: 23.04.2013
Сообщений: 18
#1

Хочу постичь дзен, необходима консультация - C++

17.09.2013, 17:33. Просмотров 345. Ответов 4
Метки нет (Все метки)

В массиве целых чисел найти непрерывный подмассив, сумма элементов которого максимальна. Необходимо вывести получившуюся сумму и два индекса - номера начального и конечного элементов массива. Все элементы пронумерованы попорядку, начиная с 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
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
#include <stdio.h>
#include <algorithm>
 
int main()
{
        FILE *f;
 
        f = fopen("input.txt", "r");
 
        long a = 0;
        fscanf(f, "%d", &a);
 
        long i = 0;
        long *array = new long [a];
        for (i = 0; i < a; ++i)
        {
                fscanf(f, "%d", &array[i]);
        }
 
        fclose(f);
//начиная от сюда
        long m = array[0];
        long first = 0; long last = 0;
        long j = 0; long s = 0;
        for (j = 0, i = 0; j < a; ++j)
        {
                s += array[j];
 
                if (s < array[j])
                {
                        s = array[j];
                        i = j;
                } 
 
                if (m < s)
                {
                        first = i;
                        last = j;
                        m = s;
                }
        }
 
 
 
            f = fopen("output.txt", "w");
 
        fprintf(f, "%d\n%d %d", m, first, last);
 
        fclose(f);
 
        return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.09.2013, 17:33     Хочу постичь дзен, необходима консультация
Посмотрите здесь:

Необходима помощь на с++,одномерные и двумерные массивы C++
Необходима помошь ! Переход с каталога в подкаталог C++
C++ консультация
Просто позарез необходима поммощь! Молю, спасайте! Завтра зачёт... C++
C++ Необходима реализация изменения частоты дискретизации на С++
C++ Какая необходима книга ?
Класс строк, необходима ли инкапсуляция? C++
C++ Программа выдаёт не ту информацию, которая необходима
Необходима проверка кода программы C++
Необходима консультация C++
Необходима реализация системы синглтонов C++
C++ Работа с файлами необходима функция или просто счетчик С++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
17.09.2013, 18:09     Хочу постичь дзен, необходима консультация #2
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
 
// m, first, last - найденные сумма, начало и конец максимального подмассива
long m = array[0];
long first = 0; long last = 0;
 
// s, i, j - сумма, начало и конец рассматриваемого (текущего на каждой итерации) подмассива
long j = 0; long s = 0;
 
// идем по всему массиву
for (j = 0, i = 0; j < a; ++j)
{
    // прибавляем к текущей сумме очередной элемент массива
    s += array[j];
 
    // если вдруг после такого прибавления текущая сумма оказывается меньше элемента,
    // т.е. вся предыдущая сумма меньше 0, нафиг она нужна
    if (s < array[j])
    {
         // в общем, начинаем текущий подмассив с j-го элемента
         s = array[j];
         i = j;
    } 
 
     // ну и если текущая сумма больше той, что считается максимальной,
     // запомним все текущие параметры, как соответствующие максимальным
     if (m < s)
     {
         first = i;
         last = j;
         m = s;
     }
}
Смотреть алгоритм 2
Василицк
0 / 0 / 0
Регистрация: 23.04.2013
Сообщений: 18
17.09.2013, 18:13  [ТС]     Хочу постичь дзен, необходима консультация #3
а ещё можно момент?
меня немного смутили эти строчки
3 long m = array[0]; -зачем нам массив?
10 for (j = 0, i = 0; j < a; ++j) - я такую запись ещё нигде не встречал
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
17.09.2013, 18:22     Хочу постичь дзен, необходима консультация #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Василицк Посмотреть сообщение
long m = array[0]; -зачем нам массив?
Ну как бы задача - найти в массиве подмассив. Массив дан изначально. Или зачем нам именно C-массив? Для наглядности наверное, так-то можно просто по одному числу из файла читать.

Цитата Сообщение от Василицк Посмотреть сообщение
for (j = 0, i = 0; j < a; ++j) - я такую запись ещё нигде не встречал
То ли еще будет :-) цикл for
Василицк
0 / 0 / 0
Регистрация: 23.04.2013
Сообщений: 18
17.09.2013, 18:28  [ТС]     Хочу постичь дзен, необходима консультация #5
Цитата Сообщение от Fyret Посмотреть сообщение
Ну как бы задача - найти в массиве подмассив. Массив дан изначально. Или зачем нам именно C-массив? Для наглядности наверное, так-то можно просто по одному числу из файла читать.


То ли еще будет :-) цикл for
а ну все, серое вещество доехало до того что нужно)
спасибо аж 2 раза)
Yandex
Объявления
17.09.2013, 18:28     Хочу постичь дзен, необходима консультация
Ответ Создать тему
Опции темы

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