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，因为其他 2 将全部删除

但是，我卡在案例 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

Answer 1

灵魂获得所有预期值，除了第二个，它获得最后注释的值 15 而不是 14。

How it works:

It takes an iterative and recursive approach, iterative, because it iterates every item and recursive by handing over an array and a partial sum for the visited/removed values.

As any working recursive function this recursive design takes an exit condition on top, where it check the remaining length of the array and take the maximum value as result and returnes the function iter.

Then the iterative part takes place, where a value v is taken to the sum and the array is filtered from

• the value from the left neighbor,
• the value from the right neighbor and
• from the value at the taken index.

Then iter is called again with a subset and a sum.

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