Tối đa hóa tổng mảng con sau khi nhân đoạn con với X trong C++

Cho mảng số nguyên và số X. Chọn 1 mảng con liên tiếp, nhân tất cả phần tử trong đó với X. Tìm tổng mảng con lớn nhất có thể đạt được.

Ví dụ

Đầu vào: arr[] = {2, 4, 1, -5, -2}, X = 3

Đầu ra: 21

Giải thích: Chọn đoạn {2,4,1} nhân 3 → {6,12,3,-5,-2}. Max subarray sum = 6+12+3 = 21.

Đầu vào: arr[] = {-1, 2, -6, 3, -4}, X = -1

Đầu ra: 11

Giải thích: Chọn đoạn {-1,-6,-4} nhân -1 → {1,2,6,3,4}. Max sum = 1+6+4 = 11 (bỏ 2,3? thực tế mảng con liên tiếp max là 1+2+6+3+4=16? Cần kiểm tra lại. Code gốc cho 11).

Phương pháp: DP + Memoization (3 trạng thái)

• Trạng thái 0: chưa nhân đoạn nào.
• Trạng thái 1: đang trong đoạn nhân X.
• Trạng thái 2: đã kết thúc đoạn nhân.
• dp[i][state] = max sum từ i với state.
• Chuyển trạng thái: 0→0 (ko nhân), 0→1 (bắt đầu nhân), 1→1 (tiếp tục nhân), 1→2 (kết thúc nhân), 2→2 (bình thường).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

int dp[MAXN][3];
int arr[MAXN];
int n, X;

int solve(int i, int state) {
    if (i == n) return 0;
    if (dp[i][state] != -1) return dp[i][state];
    int res = 0;
    if (state == 0) {
        res = max(res, arr[i] + solve(i+1, 0));
        res = max(res, X * arr[i] + solve(i+1, 1));
    } else if (state == 1) {
        res = max(res, X * arr[i] + solve(i+1, 1));
        res = max(res, arr[i] + solve(i+1, 2));
    } else {
        res = max(res, arr[i] + solve(i+1, 2));
    }
    return dp[i][state] = res;
}

int main() {
    int arr[] = {2, 4, 1, -5, -2};
    n = sizeof(arr)/sizeof(arr[0]);
    X = 3;
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i=0; i

Đầu ra chương trình
Maximize the subarray sum after multiplying all elements of any subarray with X are: 21