LeetCode之House Robber

经过抽象，我将本题的意思概括为给定一个非负整数的数组nums，在不能选取任意两个相邻的数组元素的前提下，求在该数组中选取的元素的最大和。

我采用动态规划的算法来解决此题。我把以第i个元素为结尾的最大和maxsum[i]作为子状态，并且维护两个最大值：max1和max2，其中，max1代表maxsum中前i - 1个元素的最大值，max2代表maxsum中前i个元素的最大值。当遍历到nums中的第i + 1个元素时，很自然地，maxsum[i + 1] = max1 + nums[i + 1]，然后再更新max1和max2，max1 = max2，max2 = max2 > maxsum[i + 1] ? max2 : maxsum[i + 1]。最后，遍历完nums的所有元素后，max2就是本题的解。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
				return 0;
			} else {
				int max1 = 0;
				int max2 = nums[0];

				for (int i = 1; i < nums.size(); ++i) {
					int iendmax = max1 + nums[i];

					max1 = max2;
					max2 = max2 > iendmax ? max2 : iendmax;
				}

				return max2;
			}
    }
};