C++에서 3으로 나눌 수 있는 최대 합

<시간/>

정수 배열이 있다고 가정하고 3으로 나눌 수 있도록 주어진 배열 요소의 가능한 최대 합을 찾아야 합니다. 따라서 입력이 [3,6,5,1,8]과 같으면 하위 배열이 [3,6,1,8]이고 합계가 18이므로 3으로 나눌 수 있으므로 출력은 18이 됩니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 배열의 크기
(n + 1) x 3 크기의 2차원 배열 dp 하나 생성
dp[0, 0] :=0, dp[0,1] :=-inf, dp[0,2] :=inf 설정
1에서 n 사이의 i에 대해;
- x :=숫자[i - 1]
- 0 ~ 2 범위의 j에 대해 dp[i, j] :=dp[i – 1, j]
- 0에서 2 사이의 j에 대해
  - k :=(x + j) 모드 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]