เพิ่มค่าอาร์เรย์ขึ้นถึงค่าที่กำหนดใน C++

โจทย์

ได้รับอาร์เรย์จำนวนเต็ม ตัวเลขหนึ่งตัว และค่าสูงสุด งานคือคำนวณค่าสูงสุดที่ได้จากอาร์เรย์ ทุกค่าในอาร์เรย์จากต้นทางสามารถบวกหรือลบจากผลลัพธ์ก่อนหน้าได้ โดยที่ในทุกจุด ผลลัพธ์ต้องไม่ต่ำกว่า 0 และไม่เกินค่าสูงสุดที่กำหนด สำหรับ Index 0 ให้ผลลัพธ์ก่อนหน้าเท่ากับตัวเลขที่กำหนด ถ้าไม่มีคำตอบ พิมพ์ -1

ถ้า arr[] = {3, 10, 6, 4, 5}, number = 1, max value = 15 ผลลัพธ์คือ 9 ตามลำดับบวกลบด้านล่าง

1 + 3 + 10 – 6 – 4 + 5

อัลกอริทึม

ใช้วิธี Recursive แก้ปัญหา

1. ที่ทุก Index มี 2 ทางเลือก: บวกหรือลบ องค์ประกอบปัจจุบันกับค่าที่ได้มาจาก Index ก่อนหน้า
2. เริ่มจาก Index 0 บวกหรือลบ arr[0] จากตัวเลขที่กำหนด เรียก Recursive สำหรับ Index ถัดไปพร้อมค่าที่ปรับแล้ว
3. เมื่อท่องจบอาร์เรย์ เปรียบเทียบค่าที่ปรับแล้วกับค่าสูงสุดรวมที่ได้จนถึงตอนนั้น

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

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

void getMaxValue(int* arr, int n, int num, int maxLimit, int idx, int& result) {
    if (idx == n) {
        result = max(result, num);
        return;
    }
    if (num - arr[idx] >= 0) {
        getMaxValue(arr, n, num - arr[idx], maxLimit, idx + 1, result);
    }
    if (num + arr[idx] <= maxLimit) {
        getMaxValue(arr, n, num + arr[idx], maxLimit, idx + 1, result);
    }
}

int getMaxValue(int* arr, int n, int num, int maxLimit) {
    int result = 0;
    int idx = 0;
    getMaxValue(arr, n, num, maxLimit, idx, result);
    return result;
}

int main() {
    int num = 1;
    int arr[] = {3, 10, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxLimit = 15;
    cout << "Maximum value = " << getMaxValue(arr, n, num, maxLimit) << endl;
    return 0;
}

ผลลัพธ์

Maximum value = 9