c++ - Codility MinAbsSum

我尝试了此Codility测试:MinAbsSum。
https://codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/

我通过搜索所有可能性树来解决了这个问题。结果还可以，但是，由于大量输入超时，我的解决方案失败了。换句话说，时间复杂度没有预期的好。我的解决方案是O(nlogn)，这对于树是正常的。但是此编码测试在“动态编程”部分中，并且必须有某种方法可以对其进行改进。我尝试先对整个集合求和，然后再使用此信息，但是解决方案中始终缺少某些内容。有人对如何使用DP改善我的解决方案有想法吗？

#include <vector>
using namespace std;

int sum(vector<int>& A, size_t i, int s)
{
   if (i == A.size())
      return s;

   int tmpl = s + A[i];
   int tmpr = s - A[i];
   return min (abs(sum(A, i+1, tmpl)), abs(sum(A, i+1, tmpr)));
}

int solution(vector<int> &A) {
   return sum(A, 0, 0);
}

最佳答案

我发明了另一种解决方案，比以前的解决方案更好。我不再使用递归了。
此解决方案可以正常工作(通过了所有逻辑测试)，并且还通过了一些性能测试，但不是全部。我还能如何改善它？

#include <vector>
#include <set>
using namespace std;

int solution(vector<int> &A) {
    if (A.size() == 0) return 0;

    set<int> sums, tmpSums;
    sums.insert(abs(A[0]));
    for (auto it = begin(A) + 1; it != end(A); ++it)
    {
        for (auto s : sums)
        {
            tmpSums.insert(abs(s + abs(*it)));
            tmpSums.insert(abs(s - abs(*it)));
        }
        sums = tmpSums;
        tmpSums.clear();
    }

    return *sums.begin();
}

关于c++ - Codility MinAbsSum，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44897316/