The question is from a local hackathon: I have a sorted array of positive integers in descending order. e.g (9,4,2,1). You are allowed to traverse through n elements of the array to maximize the sum(initially n = the size of the array). As you traverse the array from the beginning to the end you are allowed to stop at any moment and start from the beginning again, but the cost of doing that is that you lose 1 element from your allowance. For example in this case the best way of doing that would be 9,0,9,4. Notice that I've stopped, lost an element(hence the 0) and continued again.
I want to solve this using dynamic programming. I know how to do this using DP in O(n^2). I am looking for an algorithm that does this in a better time complexity.
You don't want to take k numbers in some interval between restarts and k + 2 numbers in some other interval between restarts; it is always at least as good to take k + 1 each time. This means that, given the number of restarts, it's immediately clear what the pattern should be (as evenly as possible).
In time O(n), it's possible to precompute the sum of each prefix of the array. Then, in time O(n), iterate through all possible restart counts, computing for each in time O(1) what the total will be by examining the sums for two adjacent prefixes and multiplying by the appropriate number of times for each.