Решение задачи Чередующаяся подпоследовательность с Codeforces

Без пояснения   Просмотров: 327

Напомним, что последовательность b является подпоследовательностью последовательности a, если b может быть получена из a путем удаления нуля или более элементов без изменения порядка оставшихся элементов. Например, если a=[1,2,1,3,1,2,1], то возможные подпоследовательности: [1,1,1,1], [3] и [1,2,1,3,1,2,1], но не [3,2,3] и [1,1,1,1,2].

Вам задана последовательность a, состоящая из n положительных и отрицательных элементов (в последовательности нет нулей).

Ваша задача выбрать максимальную по размеру (длине) чередующуюся подпоследовательность заданной последовательности (то есть знак каждого следующего элемента противоположен знаку текущего элемента, например, положительный-отрицательный-положительный и так далее или отрицательный-положительный-отрицательный и так далее). Из всех таких подпоследовательностей вам нужно выбрать ту, которая имеет максимальную сумму элементов.

Другими словами, если максимальная длина чередующейся подпоследовательности равна k, то ваша задача — найти максимальную сумму элементов какой-то чередующейся подпоследовательности длины k.

Вам нужно ответить на t независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;
#define ll long long
void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> res;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    int i = 0;
    while(i < n){
        if(a[i] < 0){
            ll mn = INT_MIN;
            while(a[i] < 0 && i < n)
                mn = max(a[i], mn), ++i;
            res.push_back(mn);
        }
        else{
            ll mn = 0;
            while(a[i] > 0 && i < n)
                mn = max(a[i], mn), ++i;
            res.push_back(mn);
        }
    }
    ll sum = 0;
    for(int i = 0; i < res.size(); ++i)
        sum += res[i];
    cout << sum;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << endl;
    }
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта