Tổng lớn nhất chia hết cho ba trong C ++

Giả sử chúng ta có một số mảng là các số nguyên, chúng ta cần tìm tổng lớn nhất có thể có của các phần tử của mảng đã cho sao cho nó chia hết cho ba. Vì vậy, nếu đầu vào là [3,6,5,1,8], thì đầu ra sẽ là 18, vì mảng con là [3,6,1,8] và tổng là 18, chia hết cho 3 .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng nums
• tạo một mảng 2d dp có kích thước (n + 1) x 3
• đặt dp [0, 0]:=0, dp [0,1]:=-inf, dp [0,2]:=inf
• cho tôi trong phạm vi từ 1 đến n;
  • x:=nums [i - 1]
  • cho j trong phạm vi 0 đến 2, dp [i, j]:=dp [i - 1, j]
  • cho j trong phạm vi 0 đến 2
    • k:=(x + j) mod 3
    • dp [i, k]:=max của dp [i, k] và dp [i - 1, j] + x
• trả về dp [n, 0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[3,6,5,1,8]

Đầu ra

18