看完昨天的题目，超狗和求会不约而同地提出的一道类似题目

O(n)时间O(1)空间找出数组a中两两不连续的元素的最大和。

我的做法是这样的，其实不知道对不对。
设置三个变量，q,p,pi分别表示相对于当前位置i时，i-2位置的最大和以及i-1位置的最大和。
pi标记在i-1位置a[i-1]是否包含在这个和里面，1表示包含，0表示不包含。

初始化q=0,p=a[0],pi=1，从下标1开始循环。
则递推式为：
         max(q+a[i],q,p)     pi = 1
t=
         max(p+a[i],p)        pi = 0
其中如果t取值为q+a[i]或p+a[i]，则pi更新为1，否则为0
q=p;
p=t;
最后返回p作为这个最大值。
 --------------------------------------------------------------
下面尝试用循环不变式(loop invariant)来证明一下它的正确性。
（其中循环不变式是p，或说：进行到i时，前面i-1个元素组成的数组中"两两不连续的元素的最大和"）
1. 初始化：当i=1时，p=a[0]，由于i-1=0,此时数组只有一个元素，显然是正确的。
2. 过程：假设p,q,pi正确地表示当前状态，则：
当pi=1时，表示p包含了a[i-1]，我们不能把a[i]加到当前最大值上。
i长度的不变式必然是q+a[i],q,p中最大值。p更新为这个最大值同时pi相应更新。

当pi=0时，表示p没有包含a[i-1]，我们可以把a[i]加到当前最大值上进行比较。
p必然代表了当前最优的结果（至少比q优，如果假设成立则此时必然有p=q），因此不必考虑q。
p更新为max(p,a[i]+p)

3. 结束：此时i=n(数组长度为0，下标为0..n-1)
循环结束，由于p代表i-1=n-1时最优值，因此此时循环不变式保持。

综合1-3，证毕。