题目大意：给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整数，使得他们的和最大，要求只能使用o(1)的空间复杂度。要求给出伪码。
看到一个非常简洁精辟代码总结
select(n) = no_select(n-1) + a[n] = select(n-2) + a[n]; no_select(n) = select(n - 1); Max_sum(n) = max(select(n), no_select(n));
也就是说，对于第n个数要不要加入最终的结果有两种情况：select和no_select。选了的话由于相邻两个不同同时入选，则对于n-1就是no_select了，就只能从n-2开始选了；不选的话跟n-1时的状态是相同的。最终的选择就是看这两种决策哪个更好。
#include<bits/stdc++.h> using namespace std; int n,num[100]; int cal(int n) { if(n<0) return 0; if(n==0) return num[0]; return max(cal(n-2)+num[n],cal(n-1)); } int main() { while(scanf("%d",&n)){ memset(num,0,sizeof(num)); for(int i=0;i<n;i++) scanf("%d",&num[i]); printf("%d\n",cal(n)); } }
原文：http://www.cnblogs.com/freinds/p/6347713.html