Maximum sum

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> array(n);
    for (auto &element : array) {
        std::cin >> element;
    }

    std::vector<int> max_sum(n);
    std::vector<int> non_included(n);
    max_sum[0] = array[0];
    non_included[0] = 0;
    for (int i = 1; i < n; ++i) {
        int old_sum = max_sum[i-1];
        int old_sum_and_included = max_sum[i-1] + non_included[i-1] + array[i];

        if (array[i] > old_sum_and_included && array[i] > old_sum) {
            max_sum[i] = array[i];
            non_included[i] = 0;
            continue;
        }

        if (old_sum > old_sum_and_included) {
            max_sum[i] = old_sum;
            non_included[i] = non_included[i-1] + array[i];
        } else {
            max_sum[i] = old_sum_and_included;
            non_included[i] = 0;
        }
    }

    if (max_sum[n-1] < 0) {
        max_sum[n-1] = *std::max_element(array.begin(), array.end());
    }
    std::cout << max_sum[n-1];
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED