javascript - 使用带有扭曲的javascript找到最大总和

Question

我目前正在研究一个函数，它将一个数字数组作为输入并输出一个 int，这是最大的附加值

catch：如果选择了 num[i]，并且 num[i-1] 和/或 num[i+1] 与 num[i] 具有相同的值，则所有具有 num[i] 邻居的相邻数字将是删除。

如果选择要删除任何元素并将其添加到总和中，则任何其他等于其中一个邻居的元素都将被删除而不添加到分数中。在第一种情况下，通过删除 2（索引 1），它的邻居为 2，因此所有 2 将在一轮中删除。

例如，如果我们有 0,2,2,2,7,2,2,2。输出应该是 2+7=9 因为其他 2s 都将被删除

但是，我坚持案例 3 和 5，我解决了案例 1、2 和 4

任何输入将不胜感激

function findMaxScore(nums){
        var curr_max = 0;
        var countNeg = 0;

        //edge case: if all numbers are < 0, return 0
        let allNeg = nums => nums.every(n => n <= 0);
        if (nums.length === 0 || allNeg(nums)){ 
            console.log("All numbers in nums are negative or =0, thus return 0");
            return 0;}

        else{
            for (var i = 0; i<nums.length; i++){
                    //if there is a 0 in the array or a negative number, move on
                    //since they don't add any positive values
                    if(nums[i]<0 || nums[i]===0){
                        nums.splice(i,1);
                        console.log("got rid of all the 0s and negative numbers, currently num is: "+ nums);
                    }

                    var leftNeighbor = nums[i-1];
                    //console.log("left neighbor: "+leftNeighbor);
                    var rightNeighbor = nums[i+1];
                    //console.log("right neighbor: "+rightNeighbor);
                    if(leftNeighbor<=0){
                        nums.splice(i-1,1);
                    }
                    if(rightNeighbor<=0){
                        nums.splice(i+1,1);
                    }
                    curr_max+= nums[i];
                    //delete all neighboring numbers that contain the same value as i-1 and i+1
                    //if the left or ride side of subarray contains the same neighboring value, 
                    //delete that number as well
                    if(nums[i]===leftNeighbor){
                        nums.splice(i-1,1);
                        if(nums[i-2]===leftNeighbor){
                            nums = nums.filter(n => n !== leftNeighbor);
                        }
                    }
                    else if(nums[i]===rightNeighbor){
                        nums.splice(i+1,1);
                        if(nums[i+2]===rightNeighbor){
                            nums = nums.filter(n => n !== rightNeighbor);
                        }
                    }

                    if(nums.length=1){
                      curr_max+= nums[i];   
                    } return curr_max;

                    console.log("current max: "+curr_max);
                    //if no nums[i-1] or nums[i+1] is not equal to nums[i]
                    //delete the neighboring numbers
                    if((leftNeighbor!=nums[i]&&rightNeighbor!=nums[i])&&nums.length>1){
                        nums.splice(i-1,1);
                        nums.splice(i,1);
                        i++;
                        //console.log("iteration number: "+(i+1)+". num is currently at index "+(i)+", with a value of: "+nums[i]);
                        //console.log("deleting value at nums[i-1]: "+ nums[i-1]+ ",index of: "+ (i-1));
                        //console.log("deleting value at nums[i+1]: "+ nums[i]+ ",index of: "+ (i));
                        curr_max+= nums[i];
                    }

                }

        }
    /*
        //check to see if the current score is the max score
        var max_so_far = curr_max;
        for (var j = i; j< nums.length; j++){
            curr_max += (nums[j]-nums[j-1]);
            max_so_far = Math.max(curr_max,max_so_far);
        }
        return max_so_far;
        */
        return curr_max;
    }


    console.log("result one: "+findMaxScore([0,1,1,5,1,1])+", expected value 6");//1+5
    console.log("result two: "+findMaxScore([1,1,1,1,1,1,1,14,1,1])+", expected value 14");//1+14
    console.log("result three: "+findMaxScore([-3,-7,3,2,3,4,3,0])+", expected value 9");//expected 9 3+3+3
    console.log("result four: "+findMaxScore([-1,-7,-9])+", expected value 0");//expected 0
    console.log("result five: "+findMaxScore([0,0,0,1,2,3,4,5,6,7,8,9,10])+", expected value 30");//expected 30 10+8+6+4+2

我的输出：

got rid of all the 0s and negative numbers, currently num is: 1,1,4,1,1
result one: 5, expected value 5
result two: 11, expected value 11
result three: 2, expected value 9
All numbers in nums are negative or =0, thus return 0
result four: 0, expected value 0
got rid of all the 0s and negative numbers, currently num is: 1,2,3,4,5,6,7,8,9,10
result five: 2, expected value 30

标签： javascriptalgorithm

Answer 1

灵魂得到所有期望的值，除了第二个它得到最后一个评论的值，15而不是14。

这个怎么运作：

它采用迭代和递归的方法，迭代，因为它通过传递数组和访问/删除值的部分和来迭代每个项目并递归。

与任何工作递归函数一样，这种递归设计在顶部采用退出条件，检查数组的剩余长度并将最大值作为结果并返回函数iter。

然后进行迭代部分，其中将一个值v作为总和并从中过滤数组

• 来自左邻居的值，
• 来自右邻居的值和
• 从所取索引处的值。

然后iter用一个子集和一个总和再次调用。

function findMaxScore(array) {
    function iter(array, sum) {
        if (!array.length) {
            max = Math.max(max, sum);
            return;
        }
        array.forEach((v, i, a) => 
            iter(
                array.filter((w, j) => w !== a[i - 1] && w !== a[i + 1] && i !== j),
                sum + v
            )
        );
    }

    var max = 0;
    iter(array.filter(v => Number.isInteger(v) && v > 0), 0);
    return max;
}

console.log("result one: " + findMaxScore([0, 1, 1, 5, 1, 1]) + ", expected value 6");//1+5
console.log("result two: " + findMaxScore([1, 1, 1, 1, 1, 1, 1, 14, 1, 1]) + ", expected value 14");//1+14
console.log("result three: " + findMaxScore([-3, -7, 3, 2, 3, 4, 3, 0]) + ", expected value 9");//expected 9 3+3+3
console.log("result four: " + findMaxScore([-1, -7, -9]) + ", expected value 0");//expected 0
console.log("result five: " + findMaxScore([0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) + ", expected value 30");//expected 30 10+8+6+4+2