fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int max_difference(vector<int>& nums) {
  7.     int n = nums.size();
  8.     int sum = 0;
  9.     for (int num : nums) {
  10.         sum += num;
  11.     }
  12.  
  13.     vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1, false));
  14.     dp[0][0] = true;
  15.  
  16.     for (int i = 1; i <= n; ++i) {
  17.         for (int j = 0; j <= sum / 2; ++j) {
  18.             if (j >= nums[i - 1]) {
  19.                 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
  20.             } else {
  21.                 dp[i][j] = dp[i - 1][j];
  22.             }
  23.         }
  24.     }
  25.  
  26.     for (int i = sum / 2; i >= 0; --i) {
  27.         if (dp[n][i]) {
  28.             return sum - 2 * i;
  29.         }
  30.     }
  31.  
  32.     return 0;
  33. }
  34.  
  35. int main() {
  36.     vector<int> nums = {1, 5, 11, 5};
  37.     cout << "最大差值为：" << max_difference(nums) << endl;
  38.     return 0;
  39. }
  40.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
最大差值为：0
https://ideone.com/O3g6Nv
language:
C++14 (clang 8.0)
created:
16 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!