เพิ่มผลรวมซับอาร์เรย์สูงสุดหลังคูณซับอาร์เรย์ใดๆ ด้วย X ใน C++

ได้รับอาร์เรย์จำนวนเต็มและตัวแปร X เลือกซับอาร์เรย์หนึ่ง คูณทุกสมาชิกด้วย X หาผลรวมซับอาร์เรย์สูงสุดที่เป็นไปได้

ตัวอย่าง

Input: arr[] = {2, 4, 1, -5, -2}, X = 3

Output: 21

คำอธิบาย: เลือกซับอาร์เรย์ {2,4,1} คูณ 3 → {6,12,3,-5,-2} Max subarray sum = 6+12+3 = 21

Input: arr[] = {-1, 2, -6, 3, -4}, X = -1

Output: 11

คำอธิบาย: เลือก {-1,-6,-4} คูณ -1 → {1,2,6,3,4} Max sum = 1+6+4 = 11

อัลกอริทึม: DP + Memoization (3 สถานะ)

• สถานะ last: 0 = ยังไม่คูณ, 1 = กำลังคูณ, 2 = คูณเสร็จแล้ว
• check(first, last, arr, memo, size, x) คืนค่า max sum จาก index first ด้วยสถานะ last
• Transition:
  • last=0: ไม่คูณ (arr[first] + check(first+1,0)) หรือ เริ่มคูณ (x*arr[first] + check(first+1,1))
  • last=1: คูณต่อ (x*arr[first] + check(first+1,1)) หรือ หยุดคูณ (arr[first] + check(first+1,2))
  • last=2: ไม่คูณต่อไป (arr[first] + check(first+1,2))
• Memoization ด้วย arr_2[size][3] เริ่มต้น -1
• ลูป i=0..size-1 หา max ของ check(i,0)

ตัวอย่างโค้ด C++

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

int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) {
    int count = 0;
    if (first == size) return 0;
    if (arr_2[first][last] != -1) return arr_2[first][last];
    if (last == 0) {
        count = max(count, arr[first] + check(first+1, 0, arr, arr_2, size, x));
        count = max(count, x * arr[first] + check(first+1, 1, arr, arr_2, size, x));
    } else if (last == 1) {
        count = max(count, x * arr[first] + check(first+1, 1, arr, arr_2, size, x));
        count = max(count, arr[first] + check(first+1, 2, arr, arr_2, size, x));
    } else {
        count = max(count, arr[first] + check(first+1, 2, arr, arr_2, size, x));
    }
    return arr_2[first][last] = count;
}

int Max_Subarray(int arr[], int size, int x) {
    int arr_2[size][3];
    int temp = 0;
    memset(arr_2, -1, sizeof arr_2);
    for (int i = 0; i < size; i++)
        temp = max(temp, check(i, 0, arr, arr_2, size, x));
    return temp;
}

int main() {
    int arr[] = {2, 4, 1, -5, -2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    cout << "Maximize the subarray sum after multiplying all elements of any subarray with X are: " << Max_Subarray(arr, size, x);
    return 0;
}

ผลลัพธ์

Maximize the subarray sum after multiplying all elements of any subarray with X are: 21