有特定差异的最大对数之和


难度级别 易得奖学金
经常问 ol石 Coursera 德里韦里 风筝 Snapdeal
排列 动态编程

问题“具有特定差异的对的最大和”表示给您一个数组 整数 和一个整数K。然后我们被要求找出独立对的最大和。 如果两个整数的绝对差小于K,我们可以将它们配对。因此,我们需要找到x对的最大和,即2x个数。

使用案列

有特定差异的最大对数之和

42, 43, 4, 5, 6, 12
96

说明

我们选择42、43和5、6。在4、5和6中有选项。因此,我们取其中的最大值,使结果= 96。

途径

这个问题要求我们找出如果将配对的某些元素配对就可以达到的最大和。 排列。 我们可以在强加条件下将元素配对,即元素的绝对差应小于K。在解决问题之前,我们 分类 数组。 这样,我们可以修剪搜索空间。 考虑我们有一个未排序的数组。 然后,我们必须遍历所有元素以配对一个元素。 但是在排序之后,我们知道最大的元素就是它之前的元素。 因此,我们检查条件是否满足。

如果条件满足,我们将前一个元素与当前元素配对,然后将问题的结果相加,直到最后一个第二个元素(来自当前元素)。 但是如果条件不满足。 我们离开配对,结果与之前的结果相同。 更正式地说,如果完成配对,则result [i] = result [i-2] + input [i] + input [i-2],否则result [i] = result [i-1]。 这是我们的结果数组 DP 数组,因为我们存储的是较小子问题的结果。 正如在自下而上的DP中所做的那样,我们结合了这些较小的子问题的结果来找到原始问题的结果。

代码

C ++代码查找具有特定差异的最大对数之和

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

Java代码查找具有特定差异的最大对数之和

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

复杂度分析

时间复杂度 

O(NlogN), 这是因为我们最初对数组进行了排序。 合并排序和其他排序算法可以对O(NlogN)中的数组进行排序。 如果为我们提供了排序的输入,则可以在O(N)时间内解决问题。

空间复杂度

上), 该空间是对数组进行排序所必需的。 即使我们没有制作DP数组,并且会对DP表使用相同的输入数组。 该解决方案仍然具有相同的空间复杂度,因为排序需要该空间。