sundeepblue
4/21/2014 - 8:52 PM

Find the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other i

Find the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 --> 2 4 6

get_sum_non_consecutive.cpp
content_copyfile_download
int get_sum_non_consecutive(int A[], int N) {
    	if(N == 1) return A[0];
	int s[100] = {0};
    
	s[0] = A[0];
	s[1] = max(A[0], A[1]);

	for(int i=2; i<N; i++) {
		s[i] = max(s[i-1], s[i-2]+A[i]);
	}
	return s[N-1];
}