В одномерном массиве, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.

))

 #include   

#include   

  

using namespace std;  

  

typedef long long ll;  

  

void solve(){  

    pair ans = {0, 0};  

    ll max_sum = 0, cur_sum = 0;  

    int k = 0, n, x;  

    cin >> n;  

    for(int i = 0; i < n; i++){  

        cin >> x;  

        if(cur_sum + x < 0){  

            k = min(n - 1, i + 1);  

            cur_sum = 0;  

        }  

        else{  

            cur_sum += x;  

            if(cur_sum > max_sum){  

                max_sum = cur_sum;  

                ans = {k, i};  

            }  

        }  

    }  

    if(cur_sum > max_sum){  

        max_sum = cur_sum;  

        ans = {k, n - 1};  

    }  

    cout

хитрая задачка.

например, для такой последовательности:
(4 -2 1 -2 1 1 1 1)
решением будет она вся с суммой 5,
а для такой:
3 -2 1 -2 (1 1 1 1)
решением будут последние четыре элемента,
а для такой:
3 -2 1 -2 (1 1 1 1) -3
решение будет спрятано где-то в середине.

алгоритм придумался такой.

сначала на лету сворачиваем монотонные последовательности:
т.е.
... -2 1 1 1 1 -3 ...
переводим в
... -2 4 -3 ...

получаем ориентированный граф без циклов:
3 → -2 → 1 → -2 → 4
в котором надо найти максимальный путь.

поэтому сначала показалось, что это NP-полная задача, так что за один проход её не решить.
но оказалось, что нет:
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%81%D0%B0%D0%BC%D0%BE%D0%BC_%D0%B4%D0%BB%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D1%83%D1%82%D0%B8#%D0%90%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B_%D0%B8_%D0%BA%D1%80%D0%B8%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BF%D1%83%D1%82%D0%B8

и что-то корявое, но всё-таки получилось:

 #include  

#include  

#include  

 

using namespace std; 

 

int main() 

{ 

    vector data = {-2, 1, 1, 1, 1, 1, 1, 3, -2, 1, 1, 1}; 

    //vector data = {4, -2, 1, -2, 4}; 

     

    // переменные для сворачивания монотонной последовательности 

    int lo, chunk = INT_MIN; 

 

    // структуры для хранения границ и сумм отрезков 

    struct { 

        int lo; 

        int hi; 

        int score; 

    } curr, best; 

 

    // максимальный отрезок до текущей позиции 

    curr = {lo : 0, hi : 0, score : INT_MIN}; 

 

    // проходим по массиву 

    for (int i = 0; i < data.size(); i++) 

    { 

        // если монотонная последовательность не начата,

        // начинаем её свёртку 

        if (chunk == INT_MIN) 

        { 

            lo = i; 

            chunk = data[i]; 

        } 

        else 

        { 

            chunk += data[i]; 

        } 

         

        // если на следующем элементе

        // монотоная последовательность заканчивается, 

        // начинаем её обработку 

        if (i == data.size() - 1 || (data[i+1] < 0 && chunk > 0 || data[i+1] > 0 && chunk < 0)) 

        { 

            // если данная последовательность - первая, 

            // инициируем ей максимальный отрезок... 

            if (curr.score == INT_MIN) 

                curr = {lo : lo, hi : i, score : chunk}; 

            else 

            { 

                // иначе считаем максимальный отрезок

                // до текущего элемента 

                if (chunk > 0) 

                { 

                    if (curr.score > 0) 

                        curr.score += chunk; 

                    else 

                    { 

                        curr.score = chunk; 

                        curr.lo = lo; 

                    } 

                } 

                else 

                    curr.score += chunk; 

            } 

 

            // если максимальный отрезок до текущего элемента

            // оказался лучше, 

            // чем ранее найденный, меняем чемпиона 

            if (curr.score > best.score) 

               best = {lo : curr.lo, hi : i, score : curr.score}; 

 

            chunk = INT_MIN; 

        } 

    } 

 

    cout