Untitled
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; }