即使学完课程,还是继续回来请教老师DP问题
来源:11-1 结语
哈哈哈蜜瓜
2018-03-10
今晚朋友做笔试碰到一条DP题:一个长度为2n的数组,任意两个元素组合,求每个组合数组的最小值加起来的最大值,比如数组[1,4,3,2],如可以组成[1,4][3,2],[4,3][1,2],[1,3][4,2],那每组最小元素最大之和就是1+3=4,代码如下:
function findMaxGroup(arr) {
if (!arr) return 0
if (arr.length <= 2) return Math.min(arr[0], arr[1])
let temp = [],
res = [],
max = 0,
k = 1;
res[0] = Math.min(arr[0], arr[1])
for (let i = 3; i < arr.length; i += 2) {
for (let j = 0; j < i; j++) {
for (let n = j + 1; n <= i; n++) {
temp.push([arr[j], arr[n]])
}
}
for (let i = 0; i < temp.length; i++) {
max = Math.max(max, Math.min.apply(null, temp[i]))
}
res[k] = max + res[k - 1]
temp = []
max = 0
k++
}
return res[res.length - 1]
}做完自己都崩溃了,时间复杂度大到没朋友,求老师指点下可以优化什么地方
写回答
1回答
-
为什么觉得就是贪心。要让最小值最大,大的数字就要尽量和大的数字配对,这样才能让大的数字在数字对中成为最小值。所以排序以后两两结合就好了。我时间有限没有严格证明,但直觉上应该没有错。复杂度O(nlogn)。
012018-03-12
相似问题