Find max sum of elements in an array ( with twist)
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
Use a recurrence that accounts for that:
dp[i] = max(dp[i - 1] + a[i], <- take two consecutives
dp[i - 2] + a[i], <- skip a[i - 1])
Base cases left as an exercise.
If you see a +ve integer add it to the sum. If you see a negative integer, then inspect the next integer pick which ever is maximum and add it to the sum.
10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3
For this add 10, 20, 30, max(-10, -50), 40 max(-50, -1) and since there is no element next to -3 discard it.
The last element will go to sum if it was +ve.