Max Sum Subarray with Partition constraint using Dynamic Programming

Question

Problem statement: Given a set of n coins of some denominations (maybe repeating, in random order), and a number k. A game is being played by a single player in the following manner: Player can choose to pick 0 to k coins contiguously but will have to leave one next coin from picking. In this manner give the highest sum of coins he/she can collect.

Input: First line contains 2 space-separated integers n and x respectively, which denote n - Size of the array x - Window size

Output: A single integer denoting the max sum the player can obtain.

Working Soln Link: Ideone

long long solve(int n, int x) {
    if (n == 0) return 0;
    long long total = accumulate(arr + 1, arr + n + 1, 0ll);
    if (x >= n) return total;
    multiset<long long> dp_x;
    for (int i = 1; i <= x + 1; i++) {
        dp[i] = arr[i];
        dp_x.insert(dp[i]);
    }
    for (int i = x + 2; i <= n; i++) {
        dp[i] = arr[i] + *dp_x.begin();
        dp_x.erase(dp_x.find(dp[i - x - 1]));
        dp_x.insert(dp[i]);
    }
    long long ans = total;
    for (int i = n - x; i <= n; i++) {
        ans = min(ans, dp[i]);
    }
    return total - ans;
}

Can someone kindly explain how this code is working i.e., how line no. 12-26 in the Ideone solution is producing the correct answer?

I have dry run the code using pen and paper and found that it's giving the correct answer but couldn't figure out the algorithm used(if any). Can someone kindly explain to me how Line No. 12-26 is producing the correct answer? Is there any technique or algorithm at use here?

I am new to DP, so if someone can point out a tutorial(YouTube video, etc) related to this kind of problem, that would be great too. Thank you.

Hanjoung Lee · Accepted Answer · 2020-08-27 11:06:08Z

1

It looks like the idea is converting the problem - You must choose at least one coin in no more than x+1 coins in a row, and make it minimal. Then the original problem's answer would just be [sum of all values] - [answer of the new problem].

Then we're ready to talk about dynamic programming. Let's define a recurrence relation for f(i) which means "the partial answer of the new problem considering 1st to i-th coins, and i-th coin is chosen". (Sorry about the bad description, edits welcome)

f(i) = a(i)                                    : if (i<=x+1)
f(i) = a(i) + min(f(i-1),f(i-2),...,f(i-x-1))  : otherwise

where a(i) is the i-th coin value

I added some comments line by line.

// NOTE f() is dp[] and a() is arr[]

long long solve(int n, int x) {
    if (n == 0) return 0;
    long long total = accumulate(arr + 1, arr + n + 1, 0ll); // get the sum
    if (x >= n) return total;
    multiset<long long> dp_x; // A min-heap (with fast random access)
    for (int i = 1; i <= x + 1; i++) { // For 1 to (x+1)th,
        dp[i] = arr[i];                // f(i) = a(i)
        dp_x.insert(dp[i]); // Push the value to the heap
    }
    for (int i = x + 2; i <= n; i++) {  // For the rest, 
        dp[i] = arr[i] + *dp_x.begin(); // f(i) = a(i) + min(...)
        dp_x.erase(dp_x.find(dp[i - x - 1])); // Erase the oldest one from the heap
        dp_x.insert(dp[i]); // Push the value to the heap, so it keeps the latest x+1 elements
    }
    long long ans = total;
    for (int i = n - x; i <= n; i++) { // Find minimum of dp[] (among candidate answers)
        ans = min(ans, dp[i]);
    }
    return total - ans;
}

Please also note that multiset is used as a min-heap. However we also need quick random-access(to erase the old ones) and multiset can do it in logarithmic time. So, the overall time complexity is O(n log x).

edited Aug 27, 2020 at 11:06

answered Aug 25, 2020 at 17:12

Hanjoung Lee

2,1601 gold badge12 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Abhishek Over a year ago

Thanks for such a detailed and great explanation. Just one small doubt... why while computing the minimum of dp[], the loop is made to run from just (n-x) to n and not 1 to n in the last loop? I mean why are we ignoring the first (n-x) numbers while calculating the minimum which is to be subtracted from the total?

Hanjoung Lee Over a year ago

You're welcome. If we look at the definition of f(i), it just counts from 1 to i and i is always chosen. So if i is less than n-x, it cannot be an answer as there must have been at least one coin to be chosen between i+1 to n. i.e. x<n-i.

Collectives™ on Stack Overflow

Max Sum Subarray with Partition constraint using Dynamic Programming

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related