CODEWITHSUNDEEP
c++dynamic-programming
Abhishek
Abhishek

Reputation: 27

Max Sum Subarray with Partition constraint using Dynamic Programming

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.

Upvotes: 0

Views: 313

Answers (1)

Hanjoung Lee
Hanjoung Lee

Reputation: 2152

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).

Upvotes: 1

Related Questions