给定N，找出最大的*奇/偶数*相加得到N

Question

我想问一个基于这个问题的后续问题：Given n, find the maximum numbers added to get n

如果我只能用奇数来求和N呢?有没有什么公式可以推广呢？谢谢!

例如，给定7，ans是1，对于7，给定16，ans是4，对于1+3+5+7，给定13，ans是3，对于1+5+7

Answer 1

我将提出解决您的问题的代码，然后尝试证明/辩护它。

  public static int maxOddSumToInt(final int n) throws IllegalArgumentException {
    if(n < 0) throw new IllegalArgumentException("n must be positive");

    LinkedList<Integer> currentNums = new LinkedList<>();
    currentNums.add(1);
    int sum = 1;
    int next = 3;
    while(sum < n) {
      currentNums.add(0, next);
      sum += next;
      next += 2;
    }
    while (sum > n) {
      int r = currentNums.remove(0);
      sum -= r;
      while(sum < n) {
        currentNums.set(0, currentNums.get(0) + 2);
        sum += 2;
      }
    }
    return currentNums.size();
  }

问题的关键在于，您只需要对目标计算最唯一的奇数的计数。因此，我们如何得到最大计数并不重要，只要我们确信我们拥有它。

使用最多数字的快速通道是使用尽可能小的数字。因此，我们希望使用1,3,5,7,9，...而不是1,9,15，例如。因此，第一步是按升序包含尽可能多的数字，直到我们达到或超过目标。如果我们成功了，那就太棒了！根据定义，这是要使用的最大大小的数字集，因为没有更小的数字可用。例如，对于输入"9"，算法将添加1，添加3，添加5，看到它达到9并返回大小为3。

如果我们超过目标，我们删除最后一个添加，因为这显然使它不再可能。通过与上面类似的逻辑，这意味着我们在(n)的任何大小的集合都不能工作，因为我们之前有最小求和集合，甚至那个集合也太大了。因此，我们尝试大小为n-1的集合。从这里开始，我们如何到达我们的目标并不重要，我们只需要检查是否有任何一组大小的n-1有效。因此，为了简单起见，我们反复增加2最近添加的内容，以查看是否达到目标。这既确保了我们不会重复一个数字(我们将最大的数字变得更大，因此它不可能成为重复的数字)，也确保了如果我们再次超过目标并需要重复此步骤，我们可以进行一次删除，并且肯定会再次低于我们的目标。

总的时间复杂度有点棘手。我想我可以说它在最坏的情况下是O(N^2)，其中N是目标的值。最坏的情况是，数字只能由它自己表示(一个大小为1的集合)，所以我们构建一个集合求和，直到我们超过它(O(N))，然后在递增的同时删除每个集合，直到再次超过它(N*O(N))。基于数字的东西可能会有一个更严格的界限，但不是在我的脑海中。

该算法没有做的一件事是优雅地处理无效输入。如果你给它一个没有解的数字，它将永远运行。如果你能想出一个简单的数字测试，你可以将它添加到顶部的非法参数异常中。