Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
785 B
2
Indexable
Never
//***********************************************************//
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int find(int i, int n, int sum, vector<int> &arr, vector<int> &dp)
{
    if (i > n - 1)
        return 0;

    if (dp[i] != -1)
        return dp[i];

    int not_take = find(i + 1, n, sum, arr, dp);
    int take = find(i + 2, n, sum, arr, dp) + arr[i];

    return dp[i] = max(take, not_take);
}

void solve()
{
    ll i, j, n, m, k, q, x;
    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector<int> dp(n, -1);
    cout << find(0, n, 0, arr, dp);
}

int main()
{

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}