即使学完课程,还是继续回来请教老师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
相似问题