Найти непрерывную последовательность с наибольшим произведением в целочисленном массиве

Question

Я пришел с приведенным ниже кодом, но он не удовлетворяет всем случаям, например ::100100

1. Массив, состоящий из всех нулей

2. Массив, имеющий отрицательные значения (это немного сложно, так как речь идет о поиске продукта, поскольку две отрицательные целые дают положительное значение)

   public static int LargestProduct(int[] arr)
   {   
       //returning arr[0] if it has only one element
       if (arr.Length == 1) return arr[0];
   
       int product = 1;
       int maxProduct = Int32.MinValue;
   
       for (int i = 0; i < arr.Length; i++)
       {
           //this block store the largest product so far when it finds 0 
           if (arr[i] == 0)
           {
               if (maxProduct < product)
               {
                   maxProduct = product;
               }
               product = 1;
           }
           else 
           {
               product *= arr[i];
           }
       }
       if (maxProduct > product)
           return maxProduct;
       else
           return product;
   }
   

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

Answer 1

Я основываю свой ответ на предположении, что если у вас есть более 1 элемента в массиве, вы захотите умножить по крайней мере 2 смежных целых числа для проверки вывода, то есть в массиве {-1, 15},вы хотите получить -15, а не 15).

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

общее число произведений в массиве из n целых чисел будет равно nC2, т. е. если есть 2 элемента, то суммарные комбинации умножения будут 1, для 3, это будет 3, для 4, это будет 6 и т. д.

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

Это должно работать для негативов и нулей.

    public static long LargestProduct(int[] arr)
    {
        if (arr.Length == 1)
            return arr[0];

        int lastNumber = 1;
        List<long> latestProducts = new List<long>();
        long maxProduct = Int64.MinValue;
        for (int i = 0; i < arr.Length; i++)
        {
            var item = arr[i];
            var latest = lastNumber * item;
            var temp = new long[latestProducts.Count];
            latestProducts.CopyTo(temp);
            latestProducts.Clear();
            foreach (var p in temp)
            {
                var product = p * item;
                if (product > maxProduct)
                    maxProduct = product;
                latestProducts.Add(product);
            }
            if (i != 0)
            {
                if (latest > maxProduct)
                    maxProduct = latest;
                latestProducts.Add(latest);
            }
            lastNumber = item;
        }
        return maxProduct;
    }

Если вы хотите, чтобы максимальный продукт также включалДобавьте один элемент, присутствующий в массиве, т.е. {-1, 15} должен быть записан как 15, тогда вы можете сравнить максимальное произведение с элементом обрабатываемого массива, и это должно дать вам максимальное произведение, если единственный элемент является максимальным числом,Это может быть достигнуто путем добавления следующего кода внутри цикла for в конце.

if (item > maxProduct)
    maxProduct = item;

Answer 2

Ваша основная проблема - 2 части. Разбейте их, и решение становится легче.

1) Найти все смежные подмножества.

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

Примером того, как вы можете это сделать, является следующий код

// will contain all contiguous subsets 
var sequences = new List<Tuple<bool, List<int>>>();

// build subsets 
foreach (int item in source)
{
    var deadCopies = new List<Tuple<bool, List<int>>>();

    foreach (var record in sequences.Where(r => r.Item1 && !r.Item2.Contains(0)))
    {
        // make a copy that is "dead"
        var deadCopy = new Tuple<bool, List<int>>(false, record.Item2.ToList());
        deadCopies.Add(deadCopy);

        record.Item2.Add(item);
    }

    sequences.Add(new Tuple<bool, List<int>>(true, new List<int> { item }));
    sequences.AddRange(deadCopies);
}

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

2) Рассчитайте произведение каждого подмножества и сравните его с максимальным значением.

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

// find subset with highest product 
int maxProduct = int.MinValue;
IEnumerable<int> maxSequence = Enumerable.Empty<int>();

foreach (var record in sequences)
{
    int product = record.Item2.Aggregate((a, b) => a * b);
    if (product > maxProduct)
    {
        maxProduct = product;
        maxSequence = record.Item2;
    }
}

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

Кроме того, я не претендую на производительность кода, это просто для иллюстрации разбивки проблемы на части.

Answer 3

это можно сделать за O(N). это основано на простой идее: вычислить минимум (minCurrent) и максимум (maxCurrent) до i. Это может быть легко изменено для соответствия условиям: {0,0,-2,0} or {-2,-3, -8} or {0,0}

a[] = {6, -3, 2, 0, 3, -2, -4, -2, 4, 5}

steps of the algorithm given below for the above array a :

private static int getMaxProduct(int[] a) {
    if (a.length == 0) {
        throw new IllegalArgumentException();
    }
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE;
    for (int current : a) {
        if (current > 0) {
            maxCurrent = maxCurrent * current;
            minCurrent = Math.min(minCurrent * current, 1);
        } else if (current == 0) {
            maxCurrent = 1;
            minCurrent = 1;
        } else {
            int x = maxCurrent;
            maxCurrent = Math.max(minCurrent * current, 1);
            minCurrent = x * current;
        }
        if (max < maxCurrent) {
            max = maxCurrent;
        }
    }
    //System.out.println(minCurrent);
    return max;
}

Answer 4

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

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

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

Чтобы учесть массив всех 0, просто используйте 0 в качестве начального maxProduct. Если массив представляет собой единственное отрицательное значение, то обработка в отдельном случае отдельного элемента будет означать, что он возвращается. После этого всегда будет положительное произведение подпоследовательности, иначе весь массив будет равен 0, и он все равно должен вернуть 0.

Answer 5

Я думаю, у вас должно быть 2 продукта одновременно - они будут отличаться по признакам. О случае, когда все значения равны нулю - в конце вы можете проверить, является ли maxProduct все еще Int32.MinValue (если Int32.MinValue действительно невозможно) Мой вариант:

int maxProduct = Int32.MinValue;
int? productWithPositiveStart = null;
int? productWithNegativeStart = null;

for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == 0)
        {
            productWithPositiveStart = null;
            productWithNegativeStart = null;
        } 
        else 
        {
            if (arr[i] > 0 && productWithPositiveStart == null) 
            {
                 productWithPositiveStart = arr[i];            
            }
            else if (productWithPositiveStart != null)
            {
                 productWithPositiveStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithPositiveStart);
            }
            if (arr[i] < 0 && productWithNegativeStart == null)
            {
                 productWithNegativeStart = arr[i];
            }
            else if (productWithNegativeStart != null) 
            {
                 productWithNegativeStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithNegativeStart);
            }
            maxProduct = Math.max(arr[i], maxProduct);
        }            
    }
 if (maxProduct == Int32.MinValue) 
 {
     maxProduct = 0;
 }