Finding minimal absolute sum of a subarray

Question

There's an array A containing (positive and negative) integers. Find a (contiguous) subarray whose elements' absolute sum is minimal, e.g.:

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

I've started by implementing a brute-force algorithm which was O(N^2) or O(N^3), though it produced correct results. But the task specifies:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

After some searching I thought that maybe Kadane's algorithm can be modified to fit this problem but I failed to do it.

My question is - is Kadane's algorithm the right way to go? If not, could you point me in the right direction (or name an algorithm that could help me here)? I don't want a ready-made code, I just need help in finding the right algorithm.

Answer 1

If you compute the partial sums such as

2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...

Then the sum of any contiguous subarray is the difference of two of the partial sums. So to find the contiguous subarray whose absolute value is minimal, I suggest that you sort the partial sums and then find the two values which are closest together, and use the positions of these two partial sums in the original sequence to find the start and end of the sub-array with smallest absolute value.

The expensive bit here is the sort, so I think this runs in time O(n * log(n)).

Answer 2

This is C++ implementation of Saksow's algorithm.

int solution(vector<int> &A) {
    vector<int> P;
    int min = 20000 ;
    int dif = 0 ;
    P.resize(A.size()+1);
    P[0] = 0;
    for(int i = 1 ; i < P.size(); i ++)
    {
        P[i] = P[i-1]+A[i-1];

    }
    sort(P.begin(),P.end());
    for(int i = 1 ; i < P.size(); i++)
    {
         dif = P[i]-P[i-1];
         if(dif<min)
         {
             min = dif;
         }
    }
    return min;
}

Answer 3

I was doing this test on Codility and I found mcdowella answer quite helpful, but not enough I have to say: so here is a 2015 answer guys!

We need to build the prefix sums of array A (called P here) like: P[0] = 0, P[1] = P[0] + A[0], P[2] = P[1] + A[1], ..., P[N] = P[N-1] + A[N-1]

The "min abs sum" of A will be the minimum absolute difference between 2 elements in P. So we just have to .sort() P and loop through it taking every time 2 successive elements. This way we have O(N + Nlog(N) + N) which equals to O(Nlog(N)).

That's it!

Answer 4

The answer is yes, Kadane's algorithm is definitely the way to go for solving your problem.

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Source - I've closely worked with a PhD student who's entire PhD thesis was devoted to the maximum subarray problem.