我需要澄清这个问题的答案,但我不能评论(不够代表)所以我问了一个新问题.希望没关系.
问题是这样的:
给定一个数组,你必须找到最大可能两个相等的和,你可以排除元素.
即1,2,3,4,6给定数组我们可以有最多两个相等的和6 + 2 = 4 + 3 + 1
即4,10,18,22,我们可以得到两个相等的和18 + 4 = 22
除了蛮力找到所有计算并检查两个可能的相等和之外,你的解决这个问题的方法是什么？
编辑1:数组元素的最大数量为N <= 50,每个元素最多可达1 <= K <= 1000
编辑2:总元素总和不能大于1000.
批准的答案说:
我建议使用DP来解决这个问题,而不是跟踪A,B(两组的大小),而是跟踪A + B,AB(两组的总和和差异).
然后,对于数组中的每个元素,尝试将其添加到A或B,或两者都不添加.
跟踪总和/差异的优点是您只需要跟踪每个差异的单个值,即您在此差异中看到的总和的最大值.
我不承诺的是:
如果这是子集求和问题,我可以用DP解决它,具有(N×P)的记忆矩阵,其中N是集合的大小,P是目标总和......
但我无法弄明白我应该如何跟踪A + B,AB(如批准答案的作者所述).哪个应该是memoization矩阵的维度？以及这有助于解决问题？
答案的作者很友好地提供了一个代码示例,但由于我不懂python(我知道java),因此很难对我进行处理.
我搜索了类似的问题，但我只发现了不适用于这种情况的对象字符串：
想要转换List<List<Integer>> list为int[][] array使用流
到目前为止我得到了这个：
int[][] array= list.stream().map(List::toArray)...
我以我发现的其他类似问题为基础。但这些使用 String 并且不能使其适用于 Integers->int：
// Example with String 1:
String[][] array = list.stream()
.map(l -> l.stream().toArray(String[]::new))
.toArray(String[][]::new);
// Example with String 2:
final List<List<String>> list = ...;
final String[][] array = list.stream().map(List::toArray).toArray(String[][]::new);