LeetCode House Robber II

LeetCode House Robber II

LeetCode House Robber II

題目

思路

思路來源於Discuss。
一是在Robber這題中的O(n)解法；
二是在Robber這題中，我們只需要分別考慮包含了nums[0]和nums[n-1]的情況即可。
注意這裡的包含並不是說Robber一定要偷num[0]或nums[n-1]，只是說考慮進去的意思。

代碼

#define max(a, b) ((a)>(b)?(a):(b))

int rob(int* nums, int numsSize) {
    if (numsSize <= 0) return 0;
    if (numsSize == 1) return nums[0];
    int evenMax, ooddMax, include0, i;
    for (i = evenMax = ooddMax = 0; i < numsSize - 1; i++)  // 包含nums[0]
        if (i % 2) ooddMax = max(ooddMax + nums[i], evenMax);
        else evenMax = max(evenMax + nums[i], ooddMax);
    include0 = max(evenMax, ooddMax);
    for (i = 1, evenMax = ooddMax = 0; i < numsSize; i++)  // 包含nums[n-1]
        if (i % 2) ooddMax = max(ooddMax + nums[i], evenMax);
        else evenMax = max(evenMax + nums[i], ooddMax);
    return max(include0, max(evenMax, ooddMax));
}