A partition algorithm for positive integers

Question

I have encountered the following problem that I found very interesting to solve:

Given an array of positive integers {a1, a2, ..., an} you are required to partition the array into 3 blocks/partitions such that the maximum of sums of integers in each partition is the minimum it can be. Restriction: you cannot alter the turn in which the numbers appear (example: if you have {2, 5, 80, 1, 200, 80, 8000, 90} one partition CANNOT be the {2, 80, 1, 90}). The program must output ONLY the maximum sum, not the partitions.

So, for example let's have the array:

{2, 80, 50, 42, 1, 1, 1, 2}

The best partitioning according to the problem is:

{ {2, 80}, {50}, {42, 1, 1, 1, 2} }

so the output of the program in this case would be 82.

I have already thought of a \$O(n^2)\$ algorithm, but isn't there any better (e.g. \$O(n)\$ or \$O(n\log n)\$) algorithm?

My \$O(n^2)\$ algorithm:

#include <stdio.h>  
#include <iostream>  

using namespace std;  

int main() {  

    int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

    cin >> n;
    arr = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total += arr[i];
    }

    // O(n^2) is the following

    for (int i = 1; i < n - 1; i++) {
        onee += arr[i - 1];
        twoo = 0;
        for (int j = i + 1; j < n; j++) {
            twoo += arr[j - 1];
            threee = total - twoo - onee;
            temp_maxx = max(max(onee, twoo), threee);
            if ((temp_maxx < maxx) || (maxx == -1))
                maxx = temp_maxx;
        }
    }

    cout << maxx;

    return 0;
}

Answer 1

Edit:Previous algorithm failed, redo the algorithm completely.

Start with a full mid part, and distribute its values to its best neighbor until it is not the greatest part:

unsigned int get_min_partition3_value(const std::vector<unsigned int>& v)
{
    const unsigned int total_sum = std::accumulate(v.begin(), v.end(), 0u);
    auto it1 = v.begin();
    auto it2 = v.end();
    unsigned int part1 = 0;
    unsigned int part2 = total_sum;
    unsigned int part3 = 0;
    unsigned int res = part2;

    while (part1 < part2 && part3 < part2) {
        res = part2; // part2 is greater than part1 and part3
        if (part1 + *it1 < part3 + *(it2 - 1)) {
            part1 += *it1;
            part2 -= *it1;
            ++it1;
        } else {
            --it2;
            part3 += *it2;
            part2 -= *it2;
        }
    }
    res = std::min(res, std::max(part1, part3));
    return res;
}

Live demo. (For C++03, replace auto by std::vector<unsigned int>::const_iterator)

Complexity is O(n).

Previous not working live example.

Answer 2

Yes, more efficient algorithms do exist.

\$O(n*\log(n))\$:

1. Let's fix the end of the first part. Now we are interested in finding the end of the second one. I claim that we need to check only two candidates: the last index such that the sum of the second part is not greater then the sum of the third part and the one immediately after it (I will not post a formal proof here, but intuitively it is clear that we want keep these two sums as close to each other as possible.

2. To do it in efficient manner, we can use a binary search and prefix sums:

   // Returns the sum of the [left, right] subarray in O(1) time.
   int getSum(int left, int right)
       // Prefix sums are used here.
       ...
   
   // Checks if the current answer is better than the current best
   // and makes appropriate updates. 
   void updateAnswer(int firstEnd, int secondEnd)
       ...
   
   // Corner cases are ignored here.
   // This piece of code just represents an idea of the algorithm, it can 
   // contain bugs.
   for (int first <- 0 ... n - 1)
       int low = first
       int high = n - 1
       while (high - low > 1)
           int mid = (low + high) / 2
           if (getSum(first + 1, mid) <= getSum(mid + 1, n - 1))
               low = mid
           else
               high = mid
       updateAnswer(first, low)
       updateAnswer(first, low + 1)
   

Now we can use the following observation: when the first variable increases in the code above, the low value either increases or stays the same, too. That's why we can apply two pointers technique and get an \$O(n)\$ time complexity.

Answer 3

Code organization

main() does everything. It would be a good idea to separate the concerns, such that main() is responsible for I/O and for calling a function that determines the optimal partition.

Variables

int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;

Those are some weird variable names! If you have some sticky keys on your keyboard, you should clean out the residue.

new int[n];

If you call new, there should be a corresponding delete[]. Better, you could use a variable-length array or a std::vector<int>.

Data representation

A useful observation to make is that you don't need to store the individual numbers. Rather, the running total is more useful. The benefit is that you can find the sum of any subarray in constant time. That is, instead of storing

2, 80, 50, 42, 1, 1, 1, 2

you should store

2, 82, 132, 174, 175, 176, 177, 179

You could always reconstruct the original list from the running totals (not that you need to do so to solve this problem).

The only concern would be overflow. You didn't specify any length or size constraints on your problem, though, so I'm not going to worry about it.

Algorithm

I suggest the following strategy:

1. Tentatively place the right split past the end of the array, and find the optimal left split. (Given the cumulative representation, partitioning an array optimally into two is easy — O(log n) using a binary search for half of the total.)
2. Move the right split to the left, and adjust the left split as necessary. (The optimal left split can only ever move left, if at all.)

The complexity of the algorithm is O(n).

#include <algorithm>
#include <iostream>
#include <iterator>

template <typename T>
T max(const T a, const T b, const T c) {
    return std::max(a, std::max(b, c));
}

/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    if (end - begin <= 1) {
        return end;
    }
    T total = *(end - 1);
    T ideal = total / 2;
    ConstIter split = std::upper_bound(begin, end, ideal);

    T aSum = std::max(*(split - 1), total - *(split - 1));
    T bSum = std::max(*split, total - *split);
    return aSum < bSum ? split - 1 : split;
}

/**
 * Given an array represented as cumulative sums, find a split
 * that produces the most equal left and right sums by considering
 * small leftward movements of the upperEstimate split point.
 */
template <typename ConstIter>
ConstIter minimaxPartition2(ConstIter begin, ConstIter end, ConstIter upperEstimate) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    const T total = *(end - 1);

    ConstIter bestSplit = upperEstimate;
    T bestSum = std::max(*(bestSplit - 1), total - *(bestSplit - 1));

    for (ConstIter split = bestSplit - 1; split >= begin; --split) {
        T sum = std::max(*(split - 1), total - *(split - 1));
        if (sum < bestSum) {
            bestSum = sum;
            bestSplit = split;
        } else {
            break;
        }
    }
    return bestSplit;
}

template <typename ConstIter>
typename std::iterator_traits<ConstIter>::value_type
minimaxPartition3(ConstIter begin, ConstIter end) {
    typedef typename std::iterator_traits<ConstIter>::value_type T;
    const T total = *(end - 1);

    ConstIter split2 = end,
              split1 = minimaxPartition2(begin, split2);
    T leftSum = *split1,
      rightSum = 0,
      best = max(leftSum, total - leftSum - rightSum, rightSum);

    while (--split2 > split1 && rightSum < best) {
        rightSum = total - *split2;
        split1 = minimaxPartition2(begin, split2, split1);
        leftSum = *split1;
        best = std::min(best, max(leftSum, total - leftSum - rightSum, rightSum));
    }
    return best;
}

int main() {
    size_t len;
    std::cin >> len;

    long cumulative[len];
    for (int sum = 0, i = 0; i < len; sum = cumulative[i++]) {
        long n;
        std::cin >> n;
        if (n <= 0) {
            return 1;
        }
        cumulative[i] = sum + n;
    }
    std::cout << minimaxPartition3(cumulative, cumulative + len) << std::endl;
    return 0;
}