Maximum Score a Mathematician can score-CodePudding

For an array A of n integers, a mathematician can perform the following moves move on the array


 1. Choose an index i(0<=i<length(A)) and add A[i] to the scores.
 2. Discard either the left partition(i.e A[0....i-1]) or the right
    partition(i.e A[i 1 ... length(A)-1]). the partition discarded can
    be empty too. The selected partition becomes the new value of A and
    is used for subsequent operations.

Starting from the initial score of 0 mathematician wishes to find the maximum score achievable after K moves.

Example: A = [4,6,-10,-1,10,-20], K = 4 Maximum Score is 19 Explanation:


 - Select A[4](0-based indexing) and keep the left subarray. Now the
   score is 10 and A = [4,6,-10,-1].
 - Select A[0] and keep the right subarray. Now Score is 10 4=14 and A =
   [6,-10,-1].
 - Select A[0] and keep the right subarray. Now the score is 14 6=20,
   and A = [-10,-1].
 - Select A[1] and then right subarray. Now score is 20-1=19 and A = []

So, after K=4 moves, the maximum score is 19

I tried a dynamic programming solution with the following subproblem and recurrence relation:


 - opt(i,j,k) = maximum score possible using element from index i to j
   in k moves
 - opt(i,j,k) = max( opt(i,j,k), a[l]   max(opt(i,l-1,k-1),
   opt(l 1,j,k-1))   for l ranging from i to j (inclusive).

the complexity of the above dp solution is: n^3k

Can you help me with a better solution?

CodePudding user response：

It's basically top k largest elements, so you don't need to sort the whole array just sort it partially. C has a built-in function nth_element() where you can get the largest elements by a range.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v{4,6,-10,-1,10,-20};
    int k = 4;
    nth_element(v.begin(), v.begin() k-1, v.end(), greater<int>()); //first n largest numbers
    
    int result = 0;
    for(int i = 0; i < k;   i) {
        result  = v[i];
    }
    
    cout<<result<<endl;

    return 0;
}

CodePudding user response：

Let M be a set of the K largest values in A. It's obvious the maximum achievable score is the sum of all the elements in M. Note that it's always possible to get such a score. The mathematician can first find M and then go through the array selecting the leftmost value in A that belongs to M and discarding the left part of the array. This proves that finding the sum of M is the answer.

You can use Quickselect to achieve O(n) performance on average. If you want to avoid the worst-case performance O(n^2) you can find M using a min heap of size K storing the K largest numbers as you iterate over A. This would lead to O(n * log(K)) time complexity.