Tích lớn nhất mảng sau khi thực hiện N-1 phép toán cho trước trong C++

Cho mảng size N. Thực hiện N-1 phép toán: chọn i,j → a[j] = a[i]*a[j] và xóa a[i], hoặc chỉ xóa a[i] (chỉ được 1 lần). Tìm dãy phép toán để giá trị cuối cùng lớn nhất.

Ý tưởng

• Loại bỏ số 0 (trừ khi toàn 0).
• Nếu số lượng số âm lẻ: loại bỏ số âm có giá trị tuyệt đối nhỏ nhất.
• Nhân các số còn lại lần lượt.

Ví dụ triển khai (C++)

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

void MaximumProduct(int a[], int n) {
    int cntneg = 0, cntzero = 0, pos = -1;
    vector<int> used(n, 0);
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) { used[i] = 1; cntzero++; }
        if (a[i] < 0) {
            cntneg++;
            if (pos == -1 || abs(a[pos]) > abs(a[i])) pos = i;
        }
    }
    if (cntneg % 2) used[pos] = 1;
    if (cntzero == n || (cntzero == n-1 && cntneg == 1)) {
        for (int i = 0; i < n-1; ++i)
            cout << 1 << " " << i+1 << " " << i+2 << endl;
        return;
    }
    int last = -1;
    for (int i = 0; i < n; ++i) if (used[i]) {
        if (last != -1) cout << 1 << " " << last+1 << " " << i+1 << endl;
        last = i;
    }
    if (last != -1) cout << 2 << " " << last+1 << endl;
    last = -1;
    for (int i = 0; i < n; ++i) if (!used[i]) {
        if (last != -1) cout << 1 << " " << last+1 << " " << i+1 << endl;
        last = i;
    }
}

int main() {
    int a[] = {5, -2, 0, 1, -3};
    int n = sizeof(a)/sizeof(a[0]);
    MaximumProduct(a, n);
    return 0;
}

Đầu ra

2 3 1 1 2 1 2 4 1 4 5