#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSumIncreasingSubsequenceWithLengthK(const vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0 || k == 0 || k > n) return 0;

    // Khởi tạo mảng dp có kích thước n x (k+1)
    vector<vector<int>> dp(n, vector<int>(k+1, 0));

    // Khởi tạo dp[i][1] bằng arr[i]
    
    for(int i = 0; i < n; i++){
        dp[i][1] = arr[i];
    }
    // Tính toán dp[i][j] cho các độ dài từ 2 đến k
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(arr[i] > arr[j]){
                for(int l = 2; l < k; l++){
                    dp[i][l] = max(dp[i][l], dp[j][l-1] + arr[i]);
                }
            }
        }
    }
    


    // Tìm giá trị lớn nhất trong dp[i][k]
    int max_sum = 0;
    for (int i = 0; i < n; ++i) {
        max_sum = max(max_sum, dp[i][k]);
    }

    return max_sum;
}

int main() {
    vector<int> arr = {2, 3, 5, 7, 3, 9};
    int k = 3; // Độ dài yêu cầu của dãy con

    int result = maxSumIncreasingSubsequenceWithLengthK(arr, k);
    cout << "Tổng lớn nhất của dãy con tăng có độ dài " << k << " là: " << result << endl;

    return 0;
}