task5.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maxProductSubsequence(const vector<int>& arr, int k) {
    int n = arr.size();
    // dp_max[i][j]: max product using first i elements, picking j elements
    // dp_min[i][j]: min product using first i elements, picking j elements
    vector<vector<long long>> dp_max(n + 1, vector<long long>(k + 1, LLONG_MIN));
    vector<vector<long long>> dp_min(n + 1, vector<long long>(k + 1, LLONG_MAX));

    for (int i = 0; i <= n; ++i) {
        dp_max[i][0] = 1;
        dp_min[i][0] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            // Не берём arr[i-1]
            dp_max[i][j] = dp_max[i-1][j];
            dp_min[i][j] = dp_min[i-1][j];
            // Берём arr[i-1]
            if (dp_max[i-1][j-1] != LLONG_MIN) {
                dp_max[i][j] = max(dp_max[i][j], max(dp_max[i-1][j-1] * arr[i-1], dp_min[i-1][j-1] * arr[i-1]));
                dp_min[i][j] = min(dp_min[i][j], min(dp_max[i-1][j-1] * arr[i-1], dp_min[i-1][j-1] * arr[i-1]));
            }
        }
    }
    return dp_max[n][k];
}

int main() {
    int n, k;
    cout << "Введите количество элементов массива и длину подпоследовательности через пробел: ";
    cin >> n >> k;
    vector<int> arr(n);
    cout << "Введите элементы массива через пробел: ";
    for (int i = 0; i < n; ++i) cin >> arr[i];
    long long result = maxProductSubsequence(arr, k);
    cout << "Максимальное произведение подпоследовательности из " << k << " элементов: " << result << endl;
    return 0;
}