Tích lớn nhất dãy con kích thước k trong C++

Mô tả bài toán

Cho mảng arr[] và số k. Tìm dãy con (không cần liên tiếp) kích thước k có tích lớn nhất.

Ví dụ: arr = {1, 5, 6, -2, 0, 4}, k = 3 → Dãy con {5, 6, 4} = 120.

Giải pháp (Sắp xếp + Chọn tham lam)

• Sắp xếp mảng.
• Xử lý theo chẵn/lẻ của k và dấu số lớn nhất:
  • k chẵn: chọn cặp từ 2 đầu (âm×âm hoặc dương×dương) cho tích lớn.
  • k lẻ:
    • Max > 0: lấy max, giảm bài toán thành k-1 chẵn.
    • Max = 0: kết quả 0.
    • Max < 0 (toàn âm): lấy k số lớn nhất (gần 0 nhất).

Ví dụ minh họa

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

int findMaxSubArrayProduct(int arr[], int n, int k) {
    sort(arr, arr + n);
    long long maxProd = 1;
    if (arr[n-1] == 0 && k % 2) return 0;
    if (arr[n-1] <= 0 && k % 2) {
        for (int i = n-1; i >= n-k; i--) maxProd *= arr[i];
        return maxProd;
    }
    int i = 0, j = n-1;
    if (k % 2) { maxProd *= arr[j--]; k--; }
    k /= 2;
    while (k--) {
        long long minprod = 1LL * arr[i] * arr[i+1];
        long long maxprod = 1LL * arr[j] * arr[j-1];
        if (minprod > maxprod) { maxProd *= minprod; i += 2; }
        else { maxProd *= maxprod; j -= 2; }
    }
    return maxProd;
}

int main() {
    int arr[] = {1, 5, 6, -2, 0, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "The maximum product of subsequence of size " << k << " is " << findMaxSubArrayProduct(arr, n, k);
    return 0;
}

Đầu ra

The maximum product of subsequence of size 3 is 120