Tích lớn nhất mảng con (có số âm) trong C++

Mô tả bài toán

Cho mảng số nguyên (dương, âm, 0). Tìm mảng con liên tiếp có tích lớn nhất.

Ví dụ: {-1, 2, -7, -5, 12, 6} → Mảng con {2, -7, -5, 12, 6} = 5040.

Giải pháp (Kadane biến thể cho tích)

• Duy trì localMax (tích lớn nhất kết thúc tại i) và localMin (tích nhỏ nhất/âm lớn nhất kết thúc tại i).
• Cập nhật theo 3 trường hợp:
  • Phần tử > 0: localMax *= val, localMin = min(1, localMin * val).
  • Phần tử < 0: hoán đổi localMax và localMin rồi nhân.
  • Phần tử = 0: reset localMax = 0, localMin = 1.
• Cập nhật maxVal toàn cục.

Ví dụ minh họa

#include <iostream>
using namespace std;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int CalcMaxProductSubArray(int arr[], int n) {
    int maxVal = -1000, localMax = 1, localMin = 1, lastMax;
    for (int i = 0; i < n; i++) {
        int currentVal = arr[i];
        if (currentVal > 0) {
            localMax *= currentVal;
            localMin = min(1, localMin * currentVal);
        } else if (currentVal < 0) {
            lastMax = localMax;
            localMax = localMin * currentVal;
            localMin = lastMax * currentVal;
        } else {
            localMin = 1; localMax = 0;
        }
        maxVal = max(maxVal, localMax);
        if (localMax <= 0) localMax = 1;
    }
    return maxVal;
}

int main() {
    int arr[] = {-1, 2, -7, -5, 12, 6};
    int n = 6;
    cout << "The maximum product Subarray is " << CalcMaxProductSubArray(arr, n);
    return 0;
}

Đầu ra

The maximum product Subarray is 5040