程序在C ++中找到两个总和相等的最大和

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个称为nums的数字列表，现在找到两组，因为它们的总和相同且为最大值，然后找到总和值。

因此，如果输入类似于nums = [2，5，4，6]，则输出将为6，因为集合为[2，4]和[6]。

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int sum = 0;
      for (int i : nums) sum += i;
      int n = nums.size();
      vector<vector<int> > dp(n + 1, vector<int>(2 * sum + 5, -1));
      dp[0][sum] = 0;
      for (int i = 1; i <= n; i++) {
         int x = nums[i - 1];
         for (int j = 0; j < 2 * sum + 5; j++) {
            if (j - x >= 0 && dp[i - 1][j - x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j - x] + x);
            }
            if (j + x < 2 * sum + 5 && dp[i - 1][j + x] != -1) {
               dp[i][j] = max(dp[i][j], dp[i - 1][j + x]);
            }
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
         }
      }
      return dp[n][sum];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 5, 4, 6};
   cout << solve(v);
}

输入值

{2, 5, 4, 6}

6

以上是 程序在C ++中找到两个总和相等的最大和 的全部内容， 来源链接： utcz.com/z/340733.html