I recently appeared for an OA at Hackerrank. The question was:

Given an array A of positive integers(1 indexed) . You are allowed to remove any number of integers from the array(possibly remove zero).
Now consider k = (sum of integers at odd position - sum of integers at even position). Our goal is to maximize this k by using the above told operation.

Ex : [10, 9, 1, 5, 15]
Here it is optimum to remove index 2 and index 4 leaving us with [10, 1, 15]. Note, now we use the new indexing to index numbers and hence we get k = (10 + 15) - (1) = 24 which is max possible.

Sadly, I was not able to solve this question during the test but found a solution later through a friend. I did get the intuition that it has to be DP but when I got to know the solution it was one of those non-traditional DPs. The ones where the transition state is not obvious and where it just doesn't make sense, as to how our state is even giving us the right answer(at least for me). I wont post the solution as of now, but if someone is interested I can reply to their comment with the answer.

Now my concern is, are there any similar questions on LC? Also, how would you approach such a problem? If you have a solution please post it with the intuition rather than explaining your code!

Thanks!