олимпиадники-информатики

У Васи есть массив целых чисел из N элементов. Он хочет вырезать из массива отрезок с максимальной суммой и подарить его маме на день рождения. Какой будет максимальная сумма?


Входные данные

В первой строке дано натуральное число n ( 1 ≤ n ≤ 10 ⁵ ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10 ⁴ .

Выходные данные


Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.

Примеры



входные данные
5-1 2 3 -2 5

выходные данные
2 5 8
Сдать задачу: https://informatics....pterid=111641#1

Все было бы просто, если бы в массиве не было отрицательных чисел, тогда ответом был бы весь массив.

Эта задача является одной из самых простых на тему Динамического Программирования(ДП).

Решение:
1)Создаем массив DP, где будем хранить МАКСИМАЛЬНУЮ сумму на отрезке, в которую входит наш элемент.
2) Идем по всем элементам массива и смотрим: Нам выгодно продолжать прошлый отрезок или начать новый? (где сумма больше) и записываем сумму на данный момент в DP[i];
3)Если сумма вышла больше максимальной найденной на данный момент, то сохраняем первый и конечный элемент нашей последовательности
4)Выводимым ответ

Код(С++):

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n] ;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}

int dp[n];int l[n] = {0};
int ans = -1e9;
dp[0] = a[0];
l[0] = 0; ans = max(a[0], ans); int ml = 0,mr = 0;
for(int i = 1; i < n; i++)
{
if(a[i] > dp[i - 1] + a[i]) l[i] = i;
else l[i] = l[i-1];
dp[i] = max(a[i], a[i] + dp[i-1]);
if(ans < dp[i])
{ml = l[i];
mr = i;}
ans = max(ans, dp[i]);
}

cout <<ml + 1 <<' '<<mr + 1 << ' '<< ans;
}