Поиск максимального подмассива

@ACTIONFENIX · Регистрация: 21.02.2015

Студворк — интернет-сервис помощи студентам

Стоит задание:

Воспользуйтесь приведенными далее идеями для разработки нерекурсивного алгоритма поиска максимального подмассива за линейное время. Начните с левого конца массива и двигайтесь вправо, отслеживая найденный к данному моменту максимальный подмассив. Зная максимальный подмассив массива A[1...j], распространите ответ на поиск максимального подмассива, заканчивающегося индексом j+1, воспользовавшись следующим наблюдением: максимальный подмассив массива A[1...j+1] представляет собой либо максимальный подмассив массива A[1...j], либо подмассив A[i...j+1] для некоторого 1<=i<=j+1. Определите максимальный подмассив вида A[i...j+1] за константное время, зная максимальный подмассив, заканчивающийся индексом j.

Я набросал код на С++:

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
double FindMaximumSubarray(double arr[], unsigned int arr_size)
{
    double max_sum = 0, sum = 0;
    for (unsigned int i = 0; i < arr_size; i++)
    {
        sum += arr[i];
        unsigned int temp_i = 0;
        double temp_sum = sum;
        while (temp_i < i)
        {
            temp_sum -= arr[temp_i];
            temp_i++;
            if (temp_sum > max_sum)
            {
                max_sum = temp_sum;
            }
        }
        if (sum > max_sum)
        {
            max_sum = sum;
        }
    }
    return max_sum;
}

Но он работает за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta \left({n}^{2} \right)$ , а не за $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta \left(n \right)$ . Я уже и не знаю, как его ускорить.

@ProgJ · 07.05.2016, 20:59

Но вы же не воспользовались предложенной идеей!
Тут оставалось подумать над одним моментом:

Сообщение от ACTIONFENIX

Определите максимальный подмассив вида A[i...j+1] за константное время, зная максимальный подмассив, заканчивающийся индексом j.

На самом деле, если в A[1..j] максимум на [j₁..j₂], то для A[i...j+1] максимумом может быть одно из трёх:
1. [j₁..j₂]
2. [j₁..j+1]
3. [j₃..j+1], где j₃>j₂
Над третьим случаем и нужно подумать. Нужно перед добавлением элемента j+1 знать при каком j₃ максимальная сумма до конца массива

@Shamil1 · 08.05.2016, 03:17

Для массива A[1...j] известно:
1. Максимальная сумма суффикса Suf_j - для подмассива A]j₃...j]
2. Максимальная сумма подмассива Max_j - для подмассива A[j₁...j₂]

Для массива A[1...j+1] имеем:
1. Максимальная сумма суффикса Suf_j+1 = max(Suf_j + A_j+1, A_j+1) - для подмассива A]j₃...j+1] или A]j+1...j+1]
2. Максимальная сумма подмассива Max_j+1 = max(Max_j+1, Suf_j+1) - для подмассива A[j₁...j₂] или подмассива из пункта 1.

@Cuellius · 09.05.2016, 16:09

Можно решить данную задачу так: идем по массиву и считаем в некоторой переменной sum текущую частичную сумму. Если в какой-то момент sum окажется отрицательной, то мы просто присвоим sum = 0. Ответ: максимум из всех значений переменной sum, получившихся при проходе по массиву.

C++
1
2
3
4
5
6
7
8
9
10
11
double FindMaximumSubarray(double a[], unsigned int n)
{
    double ans = a[0], sum = 0;
    for (unsigned int r = 0; r < n; r++) 
    {
        sum += a[r];
        ans = max(ans, sum);
        sum = max(sum, 0);
    }
    return ans;
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Shamil1 Модератор 3132 / 2279 / 469 Регистрация: 26.03.2015 Сообщений: 8,870
	08.05.2016, 03:17
	Для массива A[1...j] известно: 1. Максимальная сумма суффикса Suf_j - для подмассива A]j₃...j] 2. Максимальная сумма подмассива Max_j - для подмассива A[j₁...j₂] Для массива A[1...j+1] имеем: 1. Максимальная сумма суффикса Suf_j+1 = max(Suf_j + A_j+1, A_j+1) - для подмассива A]j₃...j+1] или A]j+1...j+1] 2. Максимальная сумма подмассива Max_j+1 = max(Max_j+1, Suf_j+1) - для подмассива A[j₁...j₂] или подмассива из пункта 1. 0