Нахождение минимальной абсолютной суммы подмассива

Там есть массив A содержащие (положительные и отрицательные) целые числа. Найдите (непрерывный) подмассив, абсолютная сумма элементов которого минимальна, например:

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

Я начал с реализации алгоритма грубой силы, который был O(N^2) или же O(N^3)Хотя это дало правильные результаты. Но задача уточняет:

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

После некоторых поисков я подумал, что, возможно, алгоритм Кадане можно изменить для решения этой проблемы, но мне не удалось это сделать.

Мой вопрос - правильный ли алгоритм алгоритма Кадане? Если нет, не могли бы вы указать мне правильное направление (или назвать алгоритм, который мог бы помочь мне здесь)? Я не хочу готовый код, мне просто нужна помощь в поиске правильного алгоритма.

Источник

11 ответов

Решение

Если вы вычислите частичные суммы такие как

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

Тогда сумма любого смежного подмассива является разностью двух частичных сумм. Поэтому, чтобы найти смежный подмассив, абсолютное значение которого минимально, я предлагаю вам отсортировать частичные суммы, а затем найти два наиболее близких значения и использовать позиции этих двух частичных сумм в исходной последовательности, чтобы найти начало и конец подмассива с наименьшим абсолютным значением.

Дорогой бит здесь такой, так что я думаю, что это идет вовремя O(n * log(n)),

Источник

Это C++ реализация алгоритма Саксова.

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;
}
Источник

Я проводил этот тест на Codility и нашел ответ mcdowella весьма полезным, но не достаточно, чтобы сказать: так вот, ребята, ответ на 2015 год!

Нам нужно построить префиксные суммы массива A (здесь он называется P), например: P[0] = 0, P[1] = P[0] + A[0], P[2] = P[1] + A[1], ..., P[N] = P[N-1] + A[N-1]

"Min abs sum" для A будет минимальной абсолютной разницей между 2 элементами в P. Так что нам просто нужно .sort() P и цикл через это занимает каждый раз 2 последовательных элемента. Таким образом, мы имеем O (N + Nlog (N) + N), что равно O (N log (N)).

Это оно!

Источник

Ответ - да, алгоритм Кадане определенно является способом решения вашей проблемы.

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

Источник - Я тесно работал с аспирантом, который полностью защитил кандидатскую диссертацию по проблеме максимального подмассива.

Источник

Вот итеративное решение в Python. Это на 100% правильно. 

 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())
Источник

Короткие сладкие и работают как шарм. Решение JavaScript / NodeJs

 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]))
Источник 
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
Источник

Вы можете запустить Kadane's algorithmдважды(или делайте это за один раз), чтобы найти минимальную и максимальную сумму, где нахождение минимума работает так же, как и максимум с обратными знаками, а затем вычислите новый максимум, сравнив их абсолютное значение.

Источник-чей-то (не помню кто) комментарий на этом сайте.

Источник 
      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;

}

Источник 
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;
}
Источник

Вот решение C, основанное на алгоритме Кадане. Надеюсь, это полезно.

#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;
}
Источник
Другие вопросы по тегам