# Codility MinAbsSliceSum

A non-empty zero-indexed array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
min abs slice is a slice whose absolute sum is minimal.
For example, array A such that:
A = 2 A = -4 A = 6 A = -3 A = 9
contains the following slices, among others:
• (0, 1), whose absolute sum = |2 + (−4)| = 2
• (0, 2), whose absolute sum = |2 + (−4) + 6| = 4
• (0, 3), whose absolute sum = |2 + (−4) + 6 + (−3)| = 1
• (1, 3), whose absolute sum = |(−4) + 6 + (−3)| = 1
• (1, 4), whose absolute sum = |(−4) + 6 + (−3) + 9| = 8
• (4, 4), whose absolute sum = |9| = 9
Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A consisting of N integers, returns the absolute sum of min abs slice.
For example, given:
A = 2 A = -4 A = 6 A = -3 A = 9
the function should return 1, as explained above.
Assume that:
• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−10,000..10,000].
Complexity:
• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).