สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มบวกและหนึ่งค่า m เราสามารถแบ่งอาร์เรย์นี้เป็นอาร์เรย์ย่อยที่อยู่ติดกันจำนวน m เราต้องคิดค้นอัลกอริทึมเพื่อลดผลรวมที่ใหญ่ที่สุดในบรรดาอาร์เรย์ย่อย m เหล่านี้
ดังนั้นถ้าอาร์เรย์คือ [7,2,4,10,9] และ m =2 ผลรวมจะเท่ากับ 19 เนื่องจากเราสามารถสร้างอาร์เรย์ย่อยสองชุดได้ เช่น [7,2,4] และ [10,9] จากนั้นอาร์เรย์ย่อยที่มีผลรวมมากที่สุดคือ 19
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน splitArray() ซึ่งจะใช้อาร์เรย์ v, m,
- n :=ขนาดของวี
- สร้างขนาดอาร์เรย์หนึ่ง dp
- สร้างผลรวมอาร์เรย์อื่นของขนาด n
- sum[0] :=v[0]
- สำหรับการเริ่มต้น i :=1 เมื่อฉัน
- sum[i] :=sum[i - 1] + v[i]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int splitArray(vector<int>& v, int m) {
int n = v.size();
vector <long long int > dp(n);
vector <long long int> sum(n);
sum[0] = v[0];
for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
dp[0] = sum[n-1];
for(int i =1;i<n;i++){
dp[i] = sum[n-1] - sum[i-1];
}
for(int i =1;i<m;i++){
for(int start = 0;start<n-i;start++){
for(int end = start+1;end<=n-i;end++){
dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
}
}
}
return dp[0];
}
};
main(){
Solution ob;
vector<int> v = {7,2,4,10,9};
cout << (ob.splitArray(v, 2));
} อินพุต
[7,2,4,10,9] 2
ผลลัพธ์
19
