Рубрики

Максимальный продукт подмассива

По заданному массиву, который содержит как положительные, так и отрицательные целые числа, найдите произведение максимального массива товара. Ожидаемая временная сложность составляет O (n), и может использоваться только O (1) дополнительное пространство.

Примеры:

Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output:   60  // The subarray is {60}

Input: arr[] = {-2, -3, 0, -2, -40}
Output:   80  // The subarray is {-2, -40}

Следующее решение предполагает, что данный входной массив всегда имеет положительный вывод. Решение работает для всех случаев, упомянутых выше. Он не работает для массивов, таких как {0, 0, -20, 0}, {0, 0, 0} и т. Д. Решение может быть легко модифицировано для обработки этого случая.
Это похоже на проблему самой большой суммы смежных подмассивов . Единственное, что следует здесь отметить, это то, что максимальный продукт также может быть получен минимальным (отрицательным) продуктом, заканчивающимся предыдущим элементом, умноженным на этот элемент. Например, в массиве {12, 2, -3, -5, -6, -2}, когда мы находимся в элементе -2, максимальный продукт равен умножению, минимальный продукт заканчивается на -6 и -2.

C ++

// C ++ программа для поиска максимального массива продуктов
#include <bits/stdc++.h>

using namespace std;

  
/ * Возвращает произведение максимального подмассива продукта.
Предполагается, что данный массив всегда имеет подмассив
с продуктом более 1 * /

int maxSubarrayProduct(int arr[], int n)

{

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

    int max_ending_here = 1;

  

    // мин отрицательный продукт заканчивается в текущей позиции

    int min_ending_here = 1;

  

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

    int max_so_far = 1;

    int flag = 0;

    / * Пройти через массив. Следующие значения

    поддерживается после i-й итерации:

    max_ending_here всегда 1 или какой-то положительный продукт

                    заканчивающийся на arr [i]

    min_ending_ здесь всегда 1 или какой-то отрицательный продукт

                    заканчивающийся на arr [i] * /

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

        / * Если этот элемент положительный, обновите max_ending_here.

        Обновите min_ending_here, только если min_ending_here есть

        отрицательный * /

        if (arr[i] > 0) {

            max_ending_here = max_ending_here * arr[i];

            min_ending_here = min(min_ending_here * arr[i], 1);

            flag = 1;

        }

  

        / * Если этот элемент равен 0, то максимальный продукт

        не может закончиться здесь, сделайте как max_ending_here и

        min_ending_here 0

        Предположение: выход всегда больше или равен

                    до 1. * /

        else if (arr[i] == 0) {

            max_ending_here = 1;

            min_ending_here = 1;

        }

  

         

       / * Если элемент отрицательный. Это сложно

        max_ending_here может быть либо 1, либо положительным.

        min_ending_here может быть 1 или отрицательным.

        следующий max_ending_here всегда будет пред.

        min_ending_here * arr [i], следующий min_ending_here

        будет 1, если prev max_ending_here равен 1, в противном случае

        следующий min_ending_here будет предыдущий max_ending_here *

        обр [я] * /

  

        else {

            int temp = max_ending_here;

            max_ending_here = max(min_ending_here * arr[i], 1);

            min_ending_here = temp * arr[i];

        }

  

        // обновляем max_so_far, если необходимо

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

    }

    if (flag == 0 && max_so_far == 1)

        return 0;

    return max_so_far;

}

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

int main()

{

    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };

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

    cout << "Maximum Sub array product is "

         << maxSubarrayProduct(arr, n);

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска максимального массива продукта
#include <stdio.h>

  
// Служебные функции для получения минимум двух целых

int min(int x, int y) { return x < y ? x : y; }

  
// Служебные функции для получения максимум двух целых

int max(int x, int y) { return x > y ? x : y; }

  
/ * Возвращает произведение максимального подмассива продукта.
Предполагается, что данный массив всегда имеет подмассив
с продуктом более 1 * /

int maxSubarrayProduct(int arr[], int n)

{

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

    int max_ending_here = 1;

  

    // мин отрицательный продукт заканчивается в текущей позиции

    int min_ending_here = 1;

  

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

    int max_so_far = 1;

    int flag = 0;

  

    / * Пройти через массив. Следующие значения

    поддерживается после i-й итерации:

    max_ending_here всегда 1 или какой-то положительный продукт

                    заканчивающийся на arr [i]

    min_ending_ здесь всегда 1 или какой-то отрицательный продукт

                    заканчивающийся на arr [i] * /

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

        / * Если этот элемент положительный, обновите max_ending_here.

        Обновите min_ending_here, только если min_ending_here есть

        отрицательный * /

        if (arr[i] > 0) {

            max_ending_here = max_ending_here * arr[i];

            min_ending_here = min(min_ending_here * arr[i], 1);

            flag = 1;

        }

  

        / * Если этот элемент равен 0, то максимальный продукт

        не может закончиться здесь, сделайте как max_ending_here и

        min_ending_here 0

        Предположение: выход всегда больше или равен

                    до 1. * /

        else if (arr[i] == 0) {

            max_ending_here = 1;

            min_ending_here = 1;

        }

  

        / * Если элемент отрицательный. Это сложно

        max_ending_here может быть либо 1, либо положительным.

        min_ending_here может быть 1 или отрицательным.

        следующий min_ending_here всегда будет пред.

        max_ending_here * arr [i] next max_ending_here

        будет 1, если предыдущий min_ending_here равен 1, в противном случае

        следующий max_ending_here будет предыдущий min_ending_here *

        обр [я] * /

        else {

            int temp = max_ending_here;

            max_ending_here = max(min_ending_here * arr[i], 1);

            min_ending_here = temp * arr[i];

        }

  

        // обновляем max_so_far, если необходимо

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

    }

    if (flag == 0 && max_so_far == 1)

        return 0;

    return max_so_far;

  

    return max_so_far;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 1, -2, -3, 0, 7, -8, -2 };

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

    printf("Maximum Sub array product is %d",

           maxSubarrayProduct(arr, n));

    return 0;

}

Джава

// Java программа для поиска максимального массива товара

import java.io.*;

  

class ProductSubarray {

  

    // Служебные функции для получения минимум двух целых

    static int min(int x, int y) { return x < y ? x : y; }

  

    // Служебные функции для получения максимум двух целых

    static int max(int x, int y) { return x > y ? x : y; }

  

    / * Возвращает произведение максимального подмассива продукта.

    Предполагается, что данный массив всегда имеет подмассив

    с продуктом более 1 * /

    static int maxSubarrayProduct(int arr[])

    {

        int n = arr.length;

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

        int max_ending_here = 1;

  

        // мин отрицательный продукт заканчивается в текущей позиции

        int min_ending_here = 1;

  

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

        int max_so_far = 1;

        int flag = 0;

  

        / * Пройти через массив. Следующий

        значения сохраняются после i-й итерации:

        max_ending_here всегда 1 или какой-то положительный продукт

                        заканчивающийся на arr [i]

        min_ending_ здесь всегда 1 или какой-то отрицательный продукт

                        заканчивающийся на arr [i] * /

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

            / * Если этот элемент положительный, обновите max_ending_here.

                Обновите min_ending_here, только если min_ending_here есть

                отрицательный * /

            if (arr[i] > 0) {

                max_ending_here = max_ending_here * arr[i];

                min_ending_here = min(min_ending_here * arr[i], 1);

                flag = 1;

            }

  

            / * Если этот элемент равен 0, то максимальный продукт не может

            конец здесь, сделать как max_ending_here и min_ending

            здесь 0

            Предположение: выход всегда больше или равен 1. * /

            else if (arr[i] == 0) {

                max_ending_here = 1;

                min_ending_here = 1;

            }

  

            / * Если элемент отрицательный. Это сложно

            max_ending_here может быть либо 1, либо положительным.

            min_ending_here может быть 1 или отрицательным.

            следующий min_ending_here всегда будет пред.

            max_ending_here * arr [i]

            следующий max_ending_here будет 1, если предыдущий

            min_ending_here 1, в противном случае

            следующий max_ending_ здесь будет

                        prev min_ending_here * arr [i] * /

            else {

                int temp = max_ending_here;

                max_ending_here = max(min_ending_here * arr[i], 1);

                min_ending_here = temp * arr[i];

            }

  

            // обновляем max_so_far, если необходимо

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

        }

  

        if (flag == 0 && max_so_far == 1)

            return 0;

        return max_so_far;

    }

  

    public static void main(String[] args)

    {

  

        int arr[] = { 1, -2, -3, 0, 7, -8, -2 };

        System.out.println("Maximum Sub array product is "

                           + maxSubarrayProduct(arr));

    }

} / * Этот код предоставлен Девешом Агравалом * /

питон

# Python программа для поиска максимального массива товара

  
# Возвращает произведение максимального массива product.
# Предполагается, что данный массив всегда имеет подмассив
# с продуктом более 1

def maxsubarrayproduct(arr):

  

    n = len(arr)

  

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

    max_ending_here = 1

  

    # мин положительное завершение товара на текущей позиции

    min_ending_here = 1

  

    # Инициализировать максимум до сих пор

    max_so_far = 1

    flag = 0

  

    # Обход по всему массиву. Следующие значения

    # поддерживаются после i-й итерации:

    # max_ending_here всегда 1 или какой-то положительный продукт

    # заканчивается на arr [i]

    # min_ending_here всегда 1 или какой-то отрицательный продукт

    # заканчивается на arr [i]

    for i in range(0, n):

  

        # Если этот элемент положительный, обновите max_ending_here.

        # Обновлять min_ending_here, только если min_ending_here есть

        # отрицательный

        if arr[i] > 0:

            max_ending_here = max_ending_here * arr[i]

            min_ending_here = min (min_ending_here * arr[i], 1)

            flag = 1

  

        # Если этот элемент равен 0, то максимальный продукт не может

        # конец здесь, сделайте как max_ending_here и min_ending_here 0

        # Предположение: выход всегда больше или равен 1.

        elif arr[i] == 0:

            max_ending_here = 1

            min_ending_here = 1

  

        # Если элемент отрицательный. Это сложно

        # max_ending_here может быть 1 или положительным.

        # min_ending_here может быть 1 или отрицательным.

        # следующий min_ending_here всегда будет прежним.

        # max_ending_here * arr [i]

        # следующий max_ending_here будет 1, если предыдущий

        # min_ending_here равно 1, в противном случае

        # следующий max_ending_here будет предыдущий min_ending_here * arr [i]

        else:

            temp = max_ending_here

            max_ending_here = max (min_ending_here * arr[i], 1)

            min_ending_here = temp * arr[i]

        if (max_so_far < max_ending_here):

            max_so_far = max_ending_here

              

    if flag == 0 and max_so_far == 1:

        return 0

    return max_so_far

  
# Функция драйвера для проверки вышеуказанной функции

arr = [1, -2, -3, 0, 7, -8, -2]

print "Maximum product subarray is", maxsubarrayproduct(arr)

  
# Этот код предоставлен Девешом Агравалом

C #

// C # программа для поиска максимального массива товара

using System;

  

class GFG {

  

    // Служебные функции для получения минимум двух целых

    static int min(int x, int y) { return x < y ? x : y; }

  

    // Служебные функции для получения максимум двух целых

    static int max(int x, int y) { return x > y ? x : y; }

  

    / * Возвращает произведение максимального подмассива продукта.

    Предполагается, что данный массив всегда имеет подмассив

    с продуктом более 1 * /

    static int maxSubarrayProduct(int[] arr)

    {

        int n = arr.Length;

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

        // позиция

        int max_ending_here = 1;

  

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

        // позиция

        int min_ending_here = 1;

  

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

        int max_so_far = 1;

        int flag = 0;

  

        / * Пройти через массив. Следующий

        значения сохраняются после i-й итерации:

        max_ending_here всегда 1 или несколько положительных

        товар заканчивается на arr [i] min_ending_here is

        всегда 1 или некоторое отрицательное окончание продукта

        с обр [я] * /

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

            / * Если этот элемент положительный, обновите

            max_ending_here. Обновление min_ending_here

            только если min_ending_here отрицательный * /

            if (arr[i] > 0) {

                max_ending_here = max_ending_here * arr[i];

                min_ending_here = min(min_ending_here

                                          * arr[i],

                                      1);

                flag = 1;

            }

  

            / * Если этот элемент равен 0, то максимальный

            продукт не может закончиться здесь, сделайте оба

            max_ending_here и min_ending_here 0

            Предположение: выход всегда больше или

            равно 1. * /

            else if (arr[i] == 0) {

                max_ending_here = 1;

                min_ending_here = 1;

            }

  

            / * Если элемент отрицательный. Это сложно

            max_ending_here может быть либо 1, либо положительным.

            min_ending_here может быть 1 или отрицательным.

            следующий min_ending_here всегда будет пред.

            max_ending_here * arr [i]

            следующий max_ending_here будет 1, если предыдущий

            min_ending_here 1, в противном случае

            следующий max_ending_ здесь будет

            prev min_ending_here * arr [i] * /

            else {

                int temp = max_ending_here;

                max_ending_here = max(min_ending_here

                                          * arr[i],

                                      1);

                min_ending_here = temp * arr[i];

            }

  

            // обновляем max_so_far, если необходимо

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

        }

  

        if (flag == 0 && max_so_far == 1)

            return 0;

  

        return max_so_far;

    }

  

    public static void Main()

    {

  

        int[] arr = { 1, -2, -3, 0, 7, -8, -2 };

  

        Console.WriteLine("Maximum Sub array product is "

                          + maxSubarrayProduct(arr));

    }

}

  
/ * Этот код предоставлен vt_m * /

PHP

<?php
// php программа для поиска максимального продукта
// Subarray

  
// Сервисные функции, чтобы получить минимум
// два целых числа

function minn ($x, $y

{

    return $x < $y? $x : $y;

}

  
// Сервисные функции, чтобы получить максимум
// два целых числа

function maxx ($x, $y

{

    return $x > $y? $x : $y

}

  
/ * Возвращает продукт максимального продукта
подмассив. Предполагается, что данный массив
всегда есть подрешетка с продуктом
более 1 *

function maxSubarrayProduct($arr, $n)

{

      

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

    // текущая позиция

    $max_ending_here = 1;

  

    // мин отрицательный продукт заканчивается

    // текущая позиция

    $min_ending_here = 1;

  

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

    $max_so_far = 1;

    $flag = 0;

  

    / * Пройти через массив.

    Следующие значения поддерживаются

    после i-й итерации:

    max_ending_here всегда 1 или

    какой-то положительный продукт, заканчивающийся на

    arr [i] min_ending_ здесь всегда

    1 или некоторое отрицательное окончание продукта

    с обр [я] * /

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

    {

          

        / * Если этот элемент положительный,

        обновить max_ending_ здесь. Обновить

        min_ending_ здесь только если

        min_ending_here отрицательный * /

        if ($arr[$i] > 0)

        {

            $max_ending_here

            $max_ending_here * $arr[$i];

              

            $min_ending_here

                min ($min_ending_here

                        * $arr[$i], 1);

            $flag = 1;

        }

  

        / * Если этот элемент равен 0, то

        максимальный продукт не может закончиться здесь,

        сделать как max_ending_here и

        min_ending_here 0

        Предположение: выход всегда

        больше или равно 1. * /

        else if ($arr[$i] == 0)

        {

            $max_ending_here = 1;

            $min_ending_here = 1;

        }

  

        / * Если элемент отрицательный. Эта

        сложно max_ending_ здесь можно

        либо быть 1, либо положительным.

        min_ending_here может быть 1 или

        отрицательный. следующий min_ending_here будет

        всегда быть пред. max_ending_here *

        arr [i] следующий max_ending_ здесь будет

        1, если предыдущий min_ending_here равен 1,

        в противном случае следующий max_ending_here будет

        быть предыдущими min_ending_here * arr [i] * /

        else

        {

            $temp = $max_ending_here;

            $max_ending_here =

                max ($min_ending_here

                        * $arr[$i], 1);

                              

            $min_ending_here =

                        $temp * $arr[$i];

        }

  

        // обновляем max_so_far, если необходимо

        if ($max_so_far < $max_ending_here)

            $max_so_far = $max_ending_here;

    }

  

    if($flag==0 && $max_so_far==1) return 0; 

    return $max_so_far;

}

  
// Программа драйвера для проверки вышеуказанной функции

    $arr = array(1, -2, -3, 0, 7, -8, -2);

    $n = sizeof($arr) / sizeof($arr[0]);

    echo("Maximum Sub array product is ");

    echo (maxSubarrayProduct($arr, $n));

  
// Этот код предоставлен нитин митталь
?>

Выход:

Maximum Sub array product is 112

Сложность времени: O (n)
Вспомогательное пространство: O (1)

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

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

Максимальный продукт подмассива

0.00 (0%) 0 votes