สมมติว่าเรามีจำนวนเต็มอาร์เรย์ เราต้องหาผลรวมสูงสุดขององค์ประกอบในอาร์เรย์ที่กำหนด เพื่อให้สามารถหารด้วยสามลงตัว ดังนั้นหากอินพุตเป็น [3,6,5,1,8] เอาต์พุตจะเป็น 18 เนื่องจากอาร์เรย์ย่อยคือ [3,6,1,8] และผลรวมคือ 18 ซึ่งหารด้วย 3 ลงตัว .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์ nums
- สร้างขนาดอาร์เรย์ 2d dp หนึ่งรายการ (n + 1) x 3
- ตั้งค่า dp[0, 0] :=0, dp[0,1] :=-inf, dp[0,2] :=inf
- สำหรับฉันอยู่ในช่วง 1 ถึง n;
- x :=nums[i - 1]
- สำหรับ j ในช่วง 0 ถึง 2, dp[i, j] :=dp[i – 1, j]
- สำหรับ j ในช่วง 0 ถึง 2
- k :=(x + j) mod 3
- dp[i, k] :=สูงสุดของ dp[i, k] และ dp[i – 1, j] + x
- ส่งคืน dp[n, 0]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n = nums.size();
int dp[n+1][3];
dp[0][0] = 0;
dp[0][1] = INT_MIN;
dp[0][2] = INT_MIN;
for(int i = 1; i <= n; i++){
int x = nums[i-1];
for(int j = 0; j < 3; j++)dp[i][j] = dp[i-1][j];
for(int j = 0; j < 3; j++){
int k = (x + j) % 3;
dp[i][k] = max(dp[i][k],dp[i-1][j] + x);
}
}
return dp[n][0];
}
};
main(){
vector<int> v = {3,6,5,1,8};
Solution ob;
cout << (ob.maxSumDivThree(v));
} อินพุต
[3,6,5,1,8]
ผลลัพธ์
18
