Maximum Sum of Non-contiguous Subsequences
// solution 1, iterative version
int get_sum(int A[], int N) {
if(N == 0) return 0;
if(N == 1) return A[0];
int *S = new int[N];
S[0] = A[0];
S[1] = max(A[0], A[1]);
for(int i=2; i<N; i++)
S[i] = max(A[i], max(S[i-1], S[i-2] + A[i])); // gist!!! cannot forget A[i]
return S[N-1];
}
// solution 2, recursive version
int get_sum2(int A[], int i) {
if(i == 0) return 0;
if(i == 1) return A[0];
return max(get_sum2(A, i-1), A[i] + get_sum2(A, i-2));
}
int main()
{
int A[] = {5, 5, 10, 40, 50, 35};
cout << get_sum(A, 6) << endl;
cout << get_sum2(A, 6);
return 0;
}