fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int maxSumDivThree(vector<int>& nums) {
  7.     vector<int> dp(3, 0);
  8.  
  9.     for (int num : nums) {
  10.         vector<int> temp = dp; 
  11.         for (int sum : temp) {
  12.             int newSum = sum + num;
  13.             int rem = newSum % 3;
  14.             dp[rem] = max(dp[rem], newSum);
  15.         }
  16.     }
  17.  
  18.     return dp[0]; 
  19. }
  20.  
  21. int main() {
  22.     vector<int> nums = {3, 6, 5, 1, 8};
  23.     cout << "Greatest sum divisible by 3: " << maxSumDivThree(nums) << endl;
  24.     return 0;
  25. }
  26.  
Success #stdin #stdout 0.01s 5236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Greatest sum divisible by 3: 18
https://ideone.com/BQs1fi
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!