即使学完课程，还是继续回来请教老师DP问题

Question

今晚朋友做笔试碰到一条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]
}

做完自己都崩溃了，时间复杂度大到没朋友，求老师指点下可以优化什么地方

Answer 1

liuyubobobo 2018-03-11 05:17:02

为什么觉得就是贪心。要让最小值最大，大的数字就要尽量和大的数字配对，这样才能让大的数字在数字对中成为最小值。所以排序以后两两结合就好了。我时间有限没有严格证明，但直觉上应该没有错。复杂度O(nlogn)。

• 提问者 哈哈哈蜜瓜 #1

  多谢老师，脑残了，这么简单居然没想到是贪心