GoLang中HouseRobber编程任务中的错误

Question

The Problem statement is fairly simple:

Given a list of integers return the maximum sum of non adjacent elements.

. For example houseRobber([5,0,0,5]) => 10 and houseRobber([2,1,2]) => 4

One solution I decided on has 2 parts:

1. Generate all viable index lists

   (eg [5,0,0,5] => [[0,2],[0,3],[1,3]])

2. Identify the maximum sum of elements at a given set of indices.

   (eg [5,0,0,5],[[0,2],[0,3],[1,3]] => 10)

So I went forth and implemented my solution. I've made the script package main and included a my own failing test so that anyone can easily run it themselves on their own machine.

package main
import(
    "fmt"
)
/*
concat takes 2 arrays of integer arrays and concatonates them.
*/
func concat(a,b [][]int) [][]int{
    for _,k := range b{
        a = append(a,k)
    }
    return a
}
/*
helper takes an array of integers inGroup which have been included to a given
sub set and an integer lastHouse which is the maximum index for the array it 
returns the array of integer arrays representing all possible sets of indices 
for non adjacent elements including the indicies provided in inGroup.
*/
func helper(inGroup []int,lastHouse int) [][]int{
    if len(inGroup) == 0 {
        return concat(helper([]int{0},lastHouse),helper([]int{1},lastHouse))
    }
    highest := inGroup[len(inGroup)-1]
    if highest <= (lastHouse-3){
        return concat(helper(append(inGroup,highest+2),lastHouse),
                      helper(append(inGroup,highest+3),lastHouse))
    }
    if highest==lastHouse-2{
        return [][]int{append(inGroup,highest+2)}
    }
    return [][]int{inGroup}
}
/*
saturated is a wrapper function for the helper that does the heavy lifting. 
*/
func saturated(n int) [][]int{
    return helper([]int{},n-1)
}
/*
Given a list of integers and a list of indicies the subSetSum function returns 
the sum of the elements at the given indicies.
*/      
func subSetSum(values, indicies []int) int{
    ret := 0
    for _,k := range indicies{
        ret += values[k]
    }
    return ret
}
/*
houseRobber is the main method, taking an array of numbers and returning an integer, 
the max sum of non adjacent elements
*/
func houseRobber(nums []int) int{
    if(len(nums) == 0){
        return 0
    }
    if(len(nums) == 1){
        return nums[0]
    }
    combos := saturated(len(nums))
    temp := 0
    ret := 0
    bestCombo := 0
    for n,k := range combos{
        temp = subSetSum(nums,k)
        if temp > ret {
            ret = temp
            bestCombo = n
        }
    }
    fmt.Println(combos[bestCombo])
    return ret
}

func main(){
        houseRobber([]int{1,2,3,4,5,6,7,8,9,10,11,12,13,14})
        houseRobber([]int{1,2,3,4,5,6,7,8,9,10,11,12,13,
                  14,15,16,17,18,19,20,21,22,23,24,25,26})
}

prints: [1 3 5 7 9 12 13] & [1 3 5 7 9 11 13 15 17 20 23 25 25] as the non-adjacent indices determined to have maximum sum. But wait! 12 and 13 are adjacent! How did that happen? The only thing appended to the inGroup arrays are the highest +2 and the highest +3, however neither 10 or 11 are contained by the array so how does 13 get there? Additionally the extra 25 on the end of the second result also seems to escape the bounds of what I think should be happening. E.g. How is highest+0 getting appended to inGroup if highest+2 and highest+3 are the only values being appended?

Obviously this bug is causing some tests to fail but the problem is not ubiquitous, as a majority of tests pass.

I am sure there is an explanation here but at the moment it is escaping me.

Answer 1

It seems you hit a subtle issue with the append function.

You should not be using append to create new arrays as you are doing in your function.

Instead, copy them and append the values to the copied array.

If you replace your calls to append to copyAndAppend as defined here:

func copyAndAppend(i []int, vals ...int) []int {
    j := make([]int, len(i), len(i)+len(vals))
    copy(j, i)
    return append(j, vals...)
}

Your code seems to work correctly.

See here for more details:

unexpected slice append behaviour