Finding minimal absolute sum of a subarray

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;
}

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!

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.

def min_abs_subarray(a):
    s = [a[0]]
    for e in a[1:]:
        s.append(s[-1] + e)
    s = sorted(s)
    min = abs(s[0])
    t = s[0]
    for x in s[1:]:
        cur = abs(x)
        min = cur if cur < min else min
        cur = abs(t-x)
        min = cur if cur < min else min
        t = x
    return min

You can run Kadane's algorithmtwice(or do it in one go) to find minimum and maximum sum where finding minimum works in same way as maximum with reversed signs and then calculate new maximum by comparing their absolute value.

Source-Someone's(dont remember who) comment in this site.

Here is an Iterative solution in python. It's 100% correct.

 def solution(A):
    memo = []
    if not len(A):
        return 0

    for ind, val in enumerate(A):
        if ind == 0:
            memo.append([val, -1*val])
        else:
            newElem = []
            for i in memo[ind - 1]:
                newElem.append(i+val)
                newElem.append(i-val)
            memo.append(newElem)
    return min(abs(n) for n in memo.pop())

Short Sweet and work like a charm. JavaScript / NodeJs solution

 function solution(A, i=0, sum =0 ) {

    //Edge case if Array is empty
    if(A.length == 0) return 0;

    // Base case. For last Array element , add and substart from sum
    //  and find min of their absolute value
    if(A.length -1 === i){
        return Math.min( Math.abs(sum + A[i]), Math.abs(sum - A[i])) ;
    }

    // Absolute value by adding the elem with the sum.
    // And recusrively move to next elem
    let plus = Math.abs(solution(A, i+1, sum+A[i]));

    // Absolute value by substracting the elem from the sum
    let minus = Math.abs(solution(A, i+1, sum-A[i]));
    return Math.min(plus, minus);
}

console.log(solution([-100, 3, 2, 4]))

Here is a C solution based on Kadane's algorithm. Hopefully its helpful.

#include <stdio.h>
int min(int a, int b)
{
  return (a >= b)? b: a;
}

int min_slice(int A[], int N) {
if (N==0 || N>1000000) 
return 0;

int minTillHere = A[0];
int minSoFar = A[0];
int i;
for(i = 1; i < N; i++){
    minTillHere = min(A[i], minTillHere + A[i]);
    minSoFar = min(minSoFar, minTillHere);
    }
return minSoFar;
}


int main(){
int A[]={3, 2, -6, 4, 0}, N = 5;
//int A[]={3, 2, 6, 4, 0}, N = 5;
//int A[]={-4, -8, -3, -2, -4, -10}, N = 6;
printf("Minimum slice = %d \n", min_slice(A,N));
return 0;
}

public static int solution(int[] A) {
    int minTillHere = A[0];
    int absMinTillHere = A[0];
    int minSoFar = A[0];
    int i;
    for(i = 1; i < A.length; i++){
        absMinTillHere = Math.min(Math.abs(A[i]),Math.abs(minTillHere + A[i]));
        minTillHere = Math.min(A[i], minTillHere + A[i]);
        minSoFar = Math.min(Math.abs(minSoFar), absMinTillHere);
        }
    return minSoFar;
}

int main()
{
int n; cin >> n;

vector<int>a(n);

for(int i = 0; i < n; i++) cin >> a[i];

long long local_min = 0, global_min = LLONG_MAX;
for(int i = 0; i < n; i++)
{
    if(abs(local_min + a[i]) > abs(a[i]))
    {
        local_min = a[i];
    }
    else local_min += a[i];

    global_min = min(global_min, abs(local_min));
}
cout << global_min << endl;

}