Рубрики

Максимальная абсолютная разница между суммой двух смежных подмассивов

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

Пример:

Input: [-2, -3, 4, -1, -2, 1, 5, -3]
Output: 12
Two subarrays are [-2, -3] and [4, -1, -2, 1, 5]

Input: [2, -1, -2, 1, -4, 2, 8]
Output: 16
Two subarrays are [-1, -2, 1, -4] and [2, 8] 

Ожидаемая сложность времени O (n).

Идея состоит в том, чтобы для каждого индекса i в данном массиве arr [0… n-1] вычислить подмассивы максимальной и минимальной суммы, которые лежат в подмассивах arr [0… i] и arr [i + 1… n-1]. Мы поддерживаем четыре массива, которые хранят максимальные и минимальные суммы в подмассивах arr [0… i] и arr [i + 1… n-1] для каждого индекса i в массиве.

leftMax[] : An element leftMax[i] of this 
            array stores the maximum value 
            in subarray arr[0..i]

leftMin[] : An element leftMin[i] of this 
            array stores the minimum value
            in subarray arr[0..i]

rightMax[] : An element rightMax[i] of this 
             array stores the maximum value 
             in subarray arr[i+1..n-1]

rightMin[] : An element rightMin[i] of this
             array stores the minimum value
             in subarray arr[i+1..n-1] 

Мы можем построить более четырех массивов за O (n) время, используя алгоритм Кадане .

    Чтобы вычислить подмассив с максимальной суммой, который лежит в arr [0… i], мы запускаем алгоритм Кадане от 0 до n-1, а чтобы найти подмассив с максимальной суммой, который лежит в arr [i + 1… n-1], мы запускаем Kadane. Алгоритм от n-1 до 0.

  1. Алгоритм Кадане можно изменить, чтобы найти минимальную абсолютную сумму подмассива. Идея состоит в том, чтобы изменить знак каждого элемента в массиве и запустить алгоритм Кадане, чтобы найти подмассив с максимальной суммой, который лежит в arr [0… i] и arr [i + 1… n-1]. Теперь инвертируйте знак максимальной найденной суммы подмассива. Это будет наша минимальная сумма подмассива. Эта идея взята отсюда .
  2. Теперь из выше четырех массивов мы можем легко найти максимальную абсолютную разницу между суммой двух смежных подмассивов. Для каждого индекса i берут максимум

    1. abs (подмассив с максимальной суммой в arr [0… i] — подмассив с минимальной суммой в arr [i + 1… n-1])
    2. abs (подмассив с минимальной суммой в arr [0… i] — подмассив с максимальной суммой в arr [i + 1… n-1])

    Ниже приведена реализация вышеуказанной идеи.

    C ++

    // C ++ программа для поиска двух непересекающихся смежных
    // подмассивы такие, что абсолютная разница
    // между суммой двух подмассивов есть максимум.
    #include <bits/stdc++.h>

    using namespace std;

      
    // Найти максимальную сумму подмассива для подмассива [0..i]
    // используя стандартный алгоритм Кадане. Эта версия
    // Алгоритм Кадане будет работать, если все числа
    // отрицательно.

    int maxLeftSubArraySum(int a[], int size, int sum[])

    {

        int max_so_far = a[0];

        int curr_max = a[0];

        sum[0] = max_so_far;

      

        for (int i = 1; i < size; i++)

        {

            curr_max = max(a[i], curr_max + a[i]);

            max_so_far = max(max_so_far, curr_max);

            sum[i] = max_so_far;

        }

      

        return max_so_far;

    }

      
    // Найти максимальную сумму подмассива для подмассива [i..n]
    // используя алгоритм Кадане. Эта версия кадана
    // Алгоритм будет работать, если все числа отрицательны

    int maxRightSubArraySum(int a[], int n, int sum[])

    {

        int max_so_far = a[n];

        int curr_max = a[n];

        sum[n] = max_so_far;

      

        for (int i = n-1; i >= 0; i--)

        {

            curr_max = max(a[i], curr_max + a[i]);

            max_so_far = max(max_so_far, curr_max);

            sum[i] = max_so_far;

        }

      

        return max_so_far;

    }

      
    // Функция находит два непересекающихся смежных
    // подмассивы такие, что абсолютная разница
    // между суммой двух подмассивов есть максимум.

    int findMaxAbsDiff(int arr[], int n)

    {

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        int leftMax[n];

        maxLeftSubArraySum(arr, n, leftMax);

      

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        int rightMax[n];

        maxRightSubArraySum(arr, n-1, rightMax);

      

        // Инвертировать массив (изменить знак), чтобы найти минимум

        // сумма подмассивов.

        int invertArr[n];

        for (int i = 0; i < n; i++)

            invertArr[i] = -arr[i];

      

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        int leftMin[n];

        maxLeftSubArraySum(invertArr, n, leftMin);

        for (int i = 0; i < n; i++)

            leftMin[i] = -leftMin[i];

      

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        int rightMin[n];

        maxRightSubArraySum(invertArr, n - 1, rightMin);

        for (int i = 0; i < n; i++)

            rightMin[i] = -rightMin[i];

      

        int result = INT_MIN;

        for (int i = 0; i < n - 1; i++)

        {

            / * Для каждого индекса i берут максимум

            1. abs (максимальная сумма подмассива, который лежит в arr [0 ... i] -

                минимальная сумма подмассива, который лежит в arr [i + 1 ... n-1])

            2. abs (минимальная сумма подмассива, который лежит в arr [0 ... i] -

                максимальная сумма подмассива, который лежит в arr [i + 1 ... n-1]) * /

            int absValue = max(abs(leftMax[i] - rightMin[i + 1]),

                            abs(leftMin[i] - rightMax[i + 1]));

            if (absValue > result)

                result = absValue;

        }

      

        return result;

    }

      
    // Драйвер программы

    int main()

    {

        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

      

        int n = sizeof(a) / sizeof(a[0]);

      

        cout << findMaxAbsDiff(a, n);

      

        return 0;

    }

    Джава

    // Java программа для поиска двух непересекающихся
    // смежные подмассивы, такие что
    // абсолютная разница

    import java.util.*;

      

    class GFG {

          

        // Найти максимальную сумму подмассива для подмассива

        // [0..i] используя стандартный алгоритм Кадане.

        // Эта версия алгоритма Кадане будет

        // работаем, если все числа отрицательны.

        static int maxLeftSubArraySum(int a[], int size, 

                                              int sum[])

        {

            int max_so_far = a[0];

            int curr_max = a[0];

            sum[0] = max_so_far;

      

            for (int i = 1; i < size; i++) {

                curr_max = Math.max(a[i], curr_max + a[i]);

                max_so_far = Math.max(max_so_far, curr_max);

                sum[i] = max_so_far;

            }

      

            return max_so_far;

        }

      

        // Найти максимальную сумму подмассива для подмассива [i..n]

        // используя алгоритм Кадане. Эта версия кадана

        // Алгоритм будет работать, если все числа отрицательны

        static int maxRightSubArraySum(int a[], int n, int sum[])

        {

            int max_so_far = a[n];

            int curr_max = a[n];

            sum[n] = max_so_far;

      

            for (int i = n - 1; i >= 0; i--) {

                curr_max = Math.max(a[i], curr_max + a[i]);

                max_so_far = Math.max(max_so_far, curr_max);

                sum[i] = max_so_far;

            }

      

            return max_so_far;

        }

      

        // Функция находит два непересекающихся смежных

        // подмассивы такие, что абсолютная разница

        // между суммой двух подмассивов есть максимум.

        static int findMaxAbsDiff(int arr[], int n)

        {

            // создать и построить массив, который хранит

            // максимальные суммы подмассивов, лежащих в

            // arr [0 ... i]

            int leftMax[] = new int[n];

            maxLeftSubArraySum(arr, n, leftMax);

      

            // создать и построить массив, который хранит

            // максимальные суммы подмассивов, лежащих в

            // arr [i + 1 ... n-1]

            int rightMax[] = new int[n];

            maxRightSubArraySum(arr, n - 1, rightMax);

      

            // Инвертировать массив (изменить знак), чтобы найти минимум

            // сумма подмассивов.

            int invertArr[] = new int[n];

            for (int i = 0; i < n; i++)

                invertArr[i] = -arr[i];

      

            // создать и построить массив, который хранит

            // минимальные суммы подмассивов, лежащих в

            // arr [0 ... i]

            int leftMin[] = new int[n];

            maxLeftSubArraySum(invertArr, n, leftMin);

            for (int i = 0; i < n; i++)

                leftMin[i] = -leftMin[i];

      

            // создать и построить массив, который хранит

            // минимальные суммы подмассивов, лежащих в

            // arr [i + 1 ... n-1]

            int rightMin[] = new int[n];

            maxRightSubArraySum(invertArr, n - 1, rightMin);

            for (int i = 0; i < n; i++)

                rightMin[i] = -rightMin[i];

      

            int result = -2147483648;

            for (int i = 0; i < n - 1; i++) {

                  

            / * Для каждого индекса i берут максимум

            1. abs (максимальная сумма подмассива, который лежит в arr [0 ... i] -

                минимальная сумма подмассива, который лежит в arr [i + 1 ... n-1])

            2. abs (минимальная сумма подмассива, который лежит в arr [0 ... i] -

                максимальная сумма подмассива, который лежит в arr [i + 1 ... n-1]) * /

                int absValue = Math.max(Math.abs(leftMax[i] - rightMin[i + 1]),

                                        Math.abs(leftMin[i] - rightMax[i + 1]));

                if (absValue > result)

                    result = absValue;

            }

      

            return result;

        }

          

        // код драйвера

        public static void main(String[] args)

        {

            int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

            int n = a.length;

            System.out.print(findMaxAbsDiff(a, n));

        }

    }

      
    // Этот код предоставлен Anant Agarwal.

    python3

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

      
    # Найти максимальную сумму подмассива для
    # subarray [0..i] используя стандартный
    Алгоритм Кадане. Эта версия
    # алгоритма Кадане будет работать, если
    # все числа отрицательны.

    def maxLeftSubArraySum(a, size, sum):

      

        max_so_far = a[0]

        curr_max = a[0]

        sum[0] = max_so_far

      

        for i in range(1, size):

          

            curr_max = max(a[i], curr_max + a[i])

            max_so_far = max(max_so_far, curr_max)

            sum[i] = max_so_far

          

        return max_so_far

      
    # Найти максимальную сумму подмассива для
    # subarray [i..n] используя Kadane's
    # алгоритм. Эта версия кадана
    # Алгоритм будет работать, если все числа отрицательны

    def maxRightSubArraySum(a, n, sum):

      

        max_so_far = a[n]

        curr_max = a[n]

        sum[n] = max_so_far

      

        for i in range(n - 1, -1, -1):

          

            curr_max = max(a[i], curr_max + a[i])

            max_so_far = max(max_so_far, curr_max)

            sum[i] = max_so_far

      

        return max_so_far

      
    # Функция находит два непересекающихся
    # смежных подмассивов, таких что
    # абсолютная разница между суммой
    Максимальное количество двух подмассивов.

    def findMaxAbsDiff(arr, n):

      

        # создать и построить массив, который

        # хранит максимальные суммы подмассивов

        # которые лежат в обр [0 ... я]

        leftMax = [0 for i in range(n)]

        maxLeftSubArraySum(arr, n, leftMax)

      

        # создать и построить массив, который хранит

        # максимальные суммы подмассивов, лежащих в

        # arr [i + 1 ... n-1]

        rightMax = [0 for i in range(n)]

        maxRightSubArraySum(arr, n-1, rightMax)

      

        # Инвертировать массив (изменить знак) в

        # найти минимальную сумму подмассивов.

        invertArr = [0 for i in range(n)]

        for i in range(n):

            invertArr[i] = -arr[i]

      

        # создать и построить массив, который хранит

        # минимальные суммы подмассивов, лежащих в

        # arr [0 ... i]

        leftMin = [0 for i in range(n)]

        maxLeftSubArraySum(invertArr, n, leftMin)

        for i in range(n):

            leftMin[i] = -leftMin[i]

      

        # создать и построить массив, который хранит

        # минимальные суммы подмассивов, лежащих в

        # arr [i + 1 ... n-1]

        rightMin = [0 for i in range(n)]

        maxRightSubArraySum(invertArr, n - 1, rightMin)

        for i in range(n):

            rightMin[i] = -rightMin[i]

      

        result = -2147483648

        for i in range(n - 1):

          

            '' 'Для каждого индекса i возьмите максимум

            1. abs (максимальная сумма подмассива, который лежит в arr [0 ... i] -

                минимальная сумма подмассива, который лежит в arr [i + 1 ... n-1])

            2. abs (минимальная сумма подмассива, который лежит в arr [0 ... i] -

                Максимальная сумма подмассива, который лежит в arr [i + 1 ... n-1]) '' '

            absValue = max(abs(leftMax[i] - rightMin[i + 1]),

                           abs(leftMin[i] - rightMax[i + 1]))

            if (absValue > result):

                result = absValue

          

        return result

          
    Код водителя

    a = [-2, -3, 4, -1, -2, 1, 5, -3]

    n = len(a)

    print(findMaxAbsDiff(a, n))

      
    # Этот код предоставлен Anant Agarwal.

    C #

    // C # программа для поиска двух непересекающихся
    // смежные подмассивы, такие что
    // абсолютная разница

    using System;

    class GFG {

          
    // Найти максимальную сумму подмассива для подмассива
    // [0..i] используя стандартный алгоритм Кадане.
    // Эта версия алгоритма Кадане будет
    // работаем, если все числа отрицательны.

    static int maxLeftSubArraySum(int []a, int size, 

                                          int []sum)

    {

        int max_so_far = a[0];

        int curr_max = a[0];

        sum[0] = max_so_far;

       

        for (int i = 1; i < size; i++)

        {

            curr_max = Math.Max(a[i], curr_max + a[i]);

            max_so_far = Math.Max(max_so_far, curr_max);

            sum[i] = max_so_far;

        }

       

        return max_so_far;

    }

       
    // Найти максимальную сумму подмассива для подмассива
    // [i..n] используя алгоритм Кадане.
    // Эта версия алгоритма Кадане будет
    // работаем, если все числа отрицательны

    static int maxRightSubArraySum(int []a, int n,

                                        int []sum)

    {

        int max_so_far = a[n];

        int curr_max = a[n];

        sum[n] = max_so_far;

       

        for (int i = n-1; i >= 0; i--)

        {

            curr_max = Math.Max(a[i], curr_max + a[i]);

            max_so_far = Math.Max(max_so_far, curr_max);

            sum[i] = max_so_far;

        }

       

        return max_so_far;

    }

       
    // Функция находит два непересекающихся
    // смежные подмассивы, такие что
    // абсолютная разница между суммой
    // из двух подмассивов максимально.

    static int findMaxAbsDiff(int []arr, int n)

    {

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        int []leftMax=new int[n];

        maxLeftSubArraySum(arr, n, leftMax);

       

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        int []rightMax=new int[n];

        maxRightSubArraySum(arr, n-1, rightMax);

       

        // Инвертировать массив (изменить знак), чтобы найти минимум

        // сумма подмассивов.

        int []invertArr=new int[n];

        for (int i = 0; i < n; i++)

            invertArr[i] = -arr[i];

       

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        int []leftMin=new int[n];

        maxLeftSubArraySum(invertArr, n, leftMin);

        for (int i = 0; i < n; i++)

            leftMin[i] = -leftMin[i];

       

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        int []rightMin=new int[n];

        maxRightSubArraySum(invertArr, n - 1, rightMin);

        for (int i = 0; i < n; i++)

            rightMin[i] = -rightMin[i];

       

        int result = -2147483648;

        for (int i = 0; i < n - 1; i++)

        {

            / * Для каждого индекса i берут максимум

            1. abs (максимальная сумма подмассива, который лежит в arr [0 ... i] -

                минимальная сумма подмассива, который лежит в arr [i + 1 ... n-1])

            2. abs (минимальная сумма подмассива, который лежит в arr [0 ... i] -

                максимальная сумма подмассива, который лежит в arr [i + 1 ... n-1]) * /

            int absValue = Math.Max(Math.Abs(leftMax[i] - rightMin[i + 1]),

                                   Math.Abs(leftMin[i] - rightMax[i + 1]));

            if (absValue > result)

                result = absValue;

        }

       

        return result;

    }

      
    // код драйвера

    public static void Main()

    {

        int []a= {-2, -3, 4, -1, -2, 1, 5, -3};

        int n = a.Length;

        Console.Write(findMaxAbsDiff(a, n));

    }
    }

      
    // Этот код предоставлен Anant Agarwal.

    PHP

    <?php 
    // PHP программа для поиска двух непересекающихся
    // смежные подмассивы, такие что
    // абсолютная разница между суммой
    // два подмассива максимальны.

      
    // Найти максимальную сумму подмассива для подмассива
    // [0..i] используя стандартный алгоритм Кадане.
    // Эта версия алгоритма Кадане будет
    // работаем, если все числа отрицательны

    function maxLeftSubArraySum(&$a, $size, &$sum)

    {

        $max_so_far = $a[0];

        $curr_max = $a[0];

        $sum[0] = $max_so_far;

      

        for ($i = 1; $i < $size; $i++)

        {

            $curr_max = max($a[$i], 

                            $curr_max + $a[$i]);

            $max_so_far = max($max_so_far

                              $curr_max);

            $sum[$i] = $max_so_far;

        }

      

        return $max_so_far;

    }

      
    // Найти максимальную сумму подмассива для подмассива
    // [i..n] используя алгоритм Кадане. Эта
    // версия алгоритма Кадане будет работать
    // если все числа отрицательны

    function maxRightSubArraySum(&$a, $n, &$sum)

    {

        $max_so_far = $a[$n];

        $curr_max = $a[$n];

        $sum[$n] = $max_so_far;

      

        for ($i = $n - 1; $i >= 0; $i--)

        {

            $curr_max = max($a[$i],

                            $curr_max + $a[$i]);

            $max_so_far = max($max_so_far,

                              $curr_max);

            $sum[$i] = $max_so_far;

        }

      

        return $max_so_far;

    }

      
    // Функция находит два непересекающихся
    // смежные подмассивы, такие что
    // абсолютная разница между суммой
    // два подмассива максимальны.

    function findMaxAbsDiff(&$arr, $n)

    {

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        $leftMax = array_fill(0, $n, NULL);

        maxLeftSubArraySum($arr, $n, $leftMax);

      

        // создать и построить массив, который хранит

        // максимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        $rightMax = array_fill(0, $n, NULL);

        maxRightSubArraySum($arr, $n - 1, $rightMax);

      

        // Инвертировать массив (изменить знак) в

        // найти подмассивы минимальной суммы

        $invertArr = array_fill(0, $n, NULL);

        for ($i = 0; $i < $n; $i++)

            $invertArr[$i] = -$arr[$i];

      

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [0 ... i]

        $leftMin = array_fill(0, $n, NULL);

        maxLeftSubArraySum($invertArr, $n,

                           $leftMin);

        for ($i = 0; $i < $n; $i++)

            $leftMin[$i] = -$leftMin[$i];

      

        // создать и построить массив, который хранит

        // минимальные суммы подмассивов, лежащих в

        // arr [i + 1 ... n-1]

        $rightMin = array_fill(0, $n, NULL);

        maxRightSubArraySum($invertArr

                            $n - 1, $rightMin);

        for ($i = 0; $i < $n; $i++)

            $rightMin[$i] = -$rightMin[$i];

      

        $result = PHP_INT_MIN;

        for ($i = 0; $i <$n - 1; $i++)

        {

            / * Для каждого индекса i берут максимум

            1. abs (максимальная сумма подмассива, который лежит

               в arr [0 ... i] - минимальная сумма подмассива

               который лежит в обр [я + 1 ... н-1])

            2. abs (минимальная сумма подрешетки, которая лежит

               в arr [0 ... i] - максимальная сумма подмассива

               который лежит в arr [i + 1 ... n-1]) * /

            $absValue = max(abs($leftMax[$i] -  

                                $rightMin[$i + 1]),

                            abs($leftMin[$i] - 

                                $rightMax[$i + 1]));

            if ($absValue > $result)

                $result = $absValue;

        }

      

        return $result;

    }

      
    // Код драйвера

    $a = array(-2, -3, 4, -1, -2, 1, 5, -3);

      

    $n = sizeof($a);

      

    echo findMaxAbsDiff($a, $n);

      
    // Этот код добавлен
    // ChitraNayal
    ?>


    Выход :

    12

    Сложность времени равна O (n), где n — количество элементов во входном массиве. Необходимое вспомогательное пространство O (n).

    Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

    Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    Максимальная абсолютная разница между суммой двух смежных подмассивов

    0.00 (0%) 0 votes