Find max sum of elements in an array ( with twist)

Question

Given a array with +ve and -ve integer , find the maximum sum such that you are not allowed to skip 2 contiguous elements ( i.e you have to select at least one of them to move forward).

eg :-

10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3

Output : 10+20+30-10+40-1 = 89

Answer 1

This problem can be solved using Dynamic Programming approach.

Let arr be the given array and opt be the array to store the optimal solutions. opt[i] is the maximum sum that can be obtained starting from element i, inclusive.

opt[i] = arr[i] + (some other elements after i)

Now to solve the problem we iterate the array arr backwards, each time storing the answer opt[i]. Since we cannot skip 2 contiguous elements, either element i+1 or element i+2 has to be included in opt[i].

So for each i, opt[i] = arr[i] + max(opt[i+1], opt[i+2])

See this code to understand:

int arr[n];  // array of given numbers. array size = n.
nput(arr, n);   // input the array elements (given numbers)

int opt[n+2];   // optimal solutions. 
memset(opt, 0, sizeof(opt));    // Initially set all optimal solutions to 0.

for(int i = n-1; i >= 0; i--) {
    opt[i] = arr[i] + max(opt[i+1], opt[i+2]);
}

ans = max(opt[0], opt[1])   // final answer.

Observe that opt array has n+2 elements. This is to avoid getting illegal memory access exception (memory out of bounds) when we try to access opt[i+1] and opt[i+2] for the last element (n-1).

See the working implementation of the algorithm given above