Question

link

Given an array of positive numbers, find the maximum sum of a subsequence that no 2 numbers should be adjacent.

Eg. (3, 2, 7, 10) should return 13 (3+10)

Eg. (3, 2, 5, 10, 7) should return 15 (3+5+7).

Solution

It is an modified version of “max sum subsequence”. Answer given on gfg is:

Loop for all elements in arr[] and maintain two sums ‘incl’ and ‘excl’ where:

incl = Max sum including the previous element

excl = Max sum excluding the previous element

Code

written by me

public int solve(int[] A) {
	if (A == null || A.length == 0) {
		return 0;
	} else if (A.length == 1) {
		return A[0];
	} else if (A.length == 2) {
		return Math.max(A[0], A[1]);
	}

	// prePreMax is the max non-adjacency sequence ending 2 position ahead
	// preMax is the max non-adjacency sequence ending 1 position ahead
	int prePreMax = A[0];
	int preMax = A[1];
	int ans = 0;

	for (int i = 2; i < A.length; i++) {
		ans = Math.max(ans, prePreMax + A[i]);
		// set the 2 variables: prePreMax, preMax
		int temp = preMax;
		preMax = Math.max(0, prePreMax + A[i]);
		prePreMax = Math.max(prePreMax, temp);
	}
	return ans;
}