《leetCode》：House Robber II

題目

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

思路

受上一題思路的影響，由于此時有環，意味着第一個元素和最後一個元素不能同時出現，是以，我們可以将數組分成兩部分，第一部分就是除去最後一個元素構成的數組産生一個最大值max1，第二部分就是除去第一個元素構成的數組産生一個最大值max2.最後的結果就是max(max1,max2).

int max(int a,int b){
    return a>b?a:b;
}
int maxInArr(int *nums,int numsSize){
    if(nums==NULL||numsSize<){
        return ;
    }
    int maxValue=;
    for(int i=;i<numsSize;i++){
        if(maxValue<nums[i]){
            maxValue=nums[i];
        }
    }
    return maxValue;
}
int robHelper(int *nums,int numsSize){
    if(nums==NULL||numsSize<){
        return ;
    }
    int *result=(int *)malloc(numsSize*sizeof(int));
    if(result==NULL){
        exit(EXIT_FAILURE);
    } 
    memset(result,,numsSize*sizeof(int));//初始化為0   
    for(int i=numsSize-;i>=;i--){
        if(i==numsSize-){
            result[numsSize-]=nums[numsSize-];
        }
        else if(i==numsSize-){
            result[numsSize-]=nums[numsSize-];
        }
        else if(i==numsSize-){
            result[i]=nums[i]+nums[i+];
        }
        else {
            result[i]=nums[i]+max(result[i+],result[i+]);
        }
    }
    return max(result[],result[]);
}

int rob(int* nums, int numsSize) {  
    if(nums==NULL||numsSize<){
        return ;
    }
    if(numsSize<=){
        return maxInArr(nums,numsSize);
    }
    int res1=robHelper(nums,numsSize-);//第一個元素可能參與産生最大值 
    int res2=robHelper(nums+,numsSize-);//最後一個元素可能參與産生最大值 
    return max(res1,res2); 
}