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));
}