Spoiler Alert

Hint 1

Gọi \(sum\) là tổng cả mảng \(a\)

Kết quả của bài toán là \(max(choose3, choose2)\)

Với \(choose3\) là việc chọn 1 tích 3 số \(a[i] \times a[i + 1] \times a[i + 2]\) với \(1 ≤ i ≤ n - 2\)

Với \(choose2\) là việc chọn 2 tích 2 số \(a[i] \times a[i + 1]\) và \(a[j] \times a[j + 1]\) với \(1 ≤ i ≤ i + 2 ≤ j ≤ n - 1\)

Hint 2

\(choose3 = max\{ sum - (a[i] + a[i + 1] + a[i + 2]) + (a[i] \times a[i + 1] \times a[i + 2]) \}\)

\(choose2 = max\{ sum - (a[i] + a[i + 1] + a[j] + a[j + 1]) + (a[i] \times a[i + 1] + a[j] \times a[j + 1]) \}\)

Reference AC code | \(O(n)\) time | \(O(n)\) auxiliary space | Greedy, Math

FOR (i, 0, n - 3) /// Select a[i] * a[i+1] * a[i+2]
    res = max(res, sum - (a[i] + a[i + 1] + a[i + 2]) + (a[i] * a[i + 1] * a[i + 2]));

FOR (i, 0, n - 5) /// Select a[i] * a[i+1], a[j] * a[j+1], i < j
    FOR (j, i + 2, n - 2)
        res = max(res, sum - (a[i] + a[i + 1]) + (a[i] * a[i + 1])

                           - (a[j] + a[j + 1]) + (a[j] * a[j + 1]));

Notice:

Nếu sài mảng (a) kiểu (int) thì khi nhân phải lấy (1LL * x * y) chứ không phải ll(x * y)