Given a sorted histogram of n bars, pick k bars while minimising the area enclosed with right wall

Question

Given an integer k and a sorted histogram with n bars with heights a1, a2, a3,..., an(this sequence is non-decreasing since histogram is sorted). We have to pick k bars(1 <= k <= n) out of these n bars such that the area enclosed between chosen bars and the right wall of the histogram is minimum possible.

For example, for the sequence of heights {1, 3, 5, 9}, if we chose bars with heights 1, 5; the area enclosed with right wall will be 12 units and will look something like in the image (Assume the width of bars to be 1 unit.)

After trying a few greedy approaches (which were wrong) I moved to following Dynamic Programming solution:

Define dp[i][j][last] as the minimum area when picking j bars out of first i bars from the histogram such that previous bar we took to our right had an index last.

dp[i][j][last] = min(dp[i - 1][j][last], dp[i - 1][j - 1][i] + a[i] * (last - i));

But the problem is that it's too slow, its O(n²k), so I am hoping that somebody can help me optimize it to something like O(nk) or maybe suggest some faster greedy solution.

Answer 1

Ninetails's partial solution covers some part of the answer and I figured out other few cases that I will share.

I don't have a proof of it but the optimal bars we take always form runs of the forms 1010 or 10 or 01 or 010 or 101 or the trivial 1. (Here 1 means a series of bars we took and 0 means a series of bars we didn't take)

What this means is that the optimal bars always are in either one continuous group or in two contiguous groups with one group touching the very left. I have verified this fact using a random test generator with a O(2ⁿn²) brute-force and the O(n²k) dynamic programming solution by running it for a few thousand cases.

So with this insight, we can easily find the answer in O(n * k) using prefix sum array for finding range sums efficiently. Here's the final code in C++(with few comments)

using ll = long long;
    ll n, z;
    cin >> n >> z;
    vector<ll> a(n);
    for (auto &e : a) {
        cin >> e;
    }
    assert(is_sorted(a.begin(), a.end()));

    ll stratAns, ans = INF;

    // prefix sum array
    vector<ll> pref(n + 1);
    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + a[i - 1];
    }

    stratAns = INF;

    /// strategy 1 : handles cases where runs like 10, 01, 010, 1 are optimal to choose

    for (int starting = 0; starting + z - 1 < n; ++starting) {
        int ending = starting + z - 1;
        ll curAns = 0;

        //~ for (int i = starting; i <= ending; ++i) {
            //~ curAns += a[i];
        //~ }
        // doing the same with prefix sums instead
        curAns += pref[ending + 1] - pref[starting];

        curAns += a[ending] * (n - ending - 1);
        stratAns = min(stratAns, curAns);
    }
    ans = min(ans, stratAns);

    stratAns = INF;

    /// strategy 2 : handle cases when runs 1010 and 101 are optimal

    for (int last = z - 1; last < n; ++last) {
        for (int x = 1, y = z - 1; y > 0 && x < z; x++, y--) {
            assert(x + y == z);
            ll curAns = 0;

            //~ for (int i = 0; i < x; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[x];

            curAns += a[x - 1] * (last - y + 1 - x);

            //~ for (int i = last - y + 1; i <= last; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[last + 1] - pref[last - y + 1];


            curAns += a[last] * (n - last - 1);
            stratAns = min(curAns, stratAns);
        }
    }
    ans = min(ans, stratAns);
    cout << ans << endl;