Optimal Division หาสมการหารให้ค่าสูงสุดใน C++

ให้ลิสต์จำนวนเต็มบวก การหารติดกัน เช่น [2,3,4] → 2/3/4 สามารถใส่วงเล็บได้เพื่อเปลี่ยนลำดับการคำนวณ ต้องการหาวิธีใส่วงเล็บให้ได้ค่าสูงสุด และคืนค่าเป็นสตริงนิพจน์ (ไม่มีวงเล็บซ้ำ)

ตัวอย่าง: [1000,100,10,2] → "1000/(100/10/2)"

วิธีแก้ปัญหา (Mathematical Insight)

เพื่อให้ค่าสูงสุด ต้องหารตัวแรกด้วยผลลัพธ์ของการหารตัวที่เหลือทั้งหมด (กลุ่มตัวส่วนไว้ด้วยกัน)

1. n = ขนาด nums
2. ถ้า n = 0 → ""
3. num = nums[0] เป็นสตริง
4. ถ้า n = 1 → num
5. ถ้า n = 2 → num + "/" + nums[1]
6. den = "" วน i = 1 ถึง n-1: den += nums[i] + (ถ้าไม่ใช่ตัวสุดท้าย ใส่ "/")
7. คืนค่า num + "/(" + den + ")"

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

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

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return "";
        string num = to_string(nums[0]);
        if (n == 1) return num;
        if (n == 2) return num + "/" + to_string(nums[1]);
        string den = "";
        for (int i = 1; i < n; i++) {
            den += to_string(nums[i]);
            if (i != n - 1) den += "/";
        }
        return num + "/(" + den + ")";
    }
};

int main() {
    vector<int> v = {1000,100,10,2};
    Solution ob;
    cout << ob.optimalDivision(v);
    return 0;
}

Input

[1000,100,10,2]

Output

1000/(100/10/2)