I have a question about some test cases


  • 0
    Z

    As I know, if the count of the vector is Even, the method of robber are two.
    ex:
    if the count is 4, a0,a1,a2,a3,
    so there are two method to robber, one is about a0,a2, the other one is about a1,a3.
    if the count is 4, a0,a1,a2,a3,a4,s5
    so there are two method to robber, one is about a0,a2,a4 the other one is about a1,a3,a5, right?

    I write code like(key section):

    if(!(size&0x01))
            {
                int count = size>>1;
                int sum1 = 0,sum2 = 0;
                for(int j=0;j<count;++j)
                {
                    sum1+=nums[j*2];
                    sum2+=nums[j*2+1];
                }
                return sum1>sum2?sum1:sum2;
            }
    

    i think this code is same with my analysis.
    But , for test case "1,2,3,4,5,1,2,3,4,5". the expected answer is 16?!
    There are two robber way,1~3~5~2~4 and 2~4~1~3~5,all the sum is 15
    How can we get 16 ?

    Tks!


  • 0

    for test case "1,2,3,4,5,1,2,3,4,5". the expected answer is 16?!

    3+5+3+5


  • 0
    T

    The key is this:

    if you didn't rob the previous house you can choose to rob or not rob the current house.

    which is hiding inside the problem description saying (simplified):

    don't rob two adjacent houses

    This means that your ababab vs bababa assumption is not correct.

    Test case 1,2,3,4,5,1,2,3,4,5 has a lot of possibliities including 1, 4,3, 1,3,1,3,5, 5,5, 2,5,2,5, 1,3,5, ...; the best of which is 3,5,3,5.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.