Code : K Subsequence 101

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e7;

void solve(vector<int> &a, int k) {
    int n = a.size();
    int mx = *max_element(a.begin(), a.end());

    vector<vector<int>> dp(n + 1, vector<int>(mx + 1, -inf));
    // dp[len][lst] is the maximum sum subsequence ending at lst with length
    // len.
    dp[0][0] = 0;

    for (int curr : a) {
        auto ndp = dp;
        for (int len = 0; len < n; len++) {
            for (int lst = 0; lst <= mx; lst++) {
                // Append the current element to all those subsequences.
                int nval = dp[len][lst] + curr;
                if (len > 1) {
                    nval += lst;
                }
                ndp[len + 1][curr] = max(ndp[len + 1][curr], nval);
            }
        }
        swap(dp, ndp);
    }

    int ans = 0;
    for (int lst = 1; lst <= mx; lst++) {
        ans = max(ans, dp[k][lst]);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, k);
    }
}