Найти максимальный продукт с помощью рекурсии

Question

Я видел вопрос, и мне интересно, возможно ли решить его с помощью рекурсии. Это выглядит следующим образом:

Напишите алгоритм, который при задании массива входных данных находит максимальное произведение из этих входных данных. Например:

Input: [1, 2, 3]
Output: 6 (1*2*3)

Input: [-1, 1, 2, 3]
Output: 6 (1*2*3)

Input: [-2, -1, 1, 2, 3]
Output: 12 (-2*-1*1*2*3)

Я пытаюсь найти способ использовать рекурсию для ее решения, но алгоритм, который я пробовал, не работает. Мой алгоритм, написанный на Java, выглядит следующим образом:

Integer[] array;
public int maximumProduct(int[] nums) {
   array=new Integer[nums.length];
   return multiply(nums, 0);
}

public int multiply(int[] nums, int i){
    if (array[i]!=null){
        return array[i];
    }
    if (i==(nums.length-1)){
        return nums[i];
    }
    int returnval=Math.max(nums[i]*multiply(nums, i+1), multiply(nums, i+1));
    array[i]=returnval;
    return returnval;

}

Проблема этого алгоритма в том, что он не работает хорошо, если есть четное число отрицательных чисел. Например, если nums [0] = - 2, nums [1] = - 1 и nums [2] = 1, то умножение (nums, 1) всегда будет возвращать 1 вместо -1, и, таким образом, оно всегда будет видеть 1 больше чем 1 * -2 при умножении (числа 0). Однако я не уверен, как решить эту проблему. Есть ли способ решить эту проблему с помощью рекурсии или динамического программирования c?

Answer 1

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

Во всех остальных случаях окончательный ответ будет положительным.

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

Все это требует только двух линейных сканирований массива и, следовательно, работает за O (n) раз.

Answer 2

Какое максимальное произведение целых чисел?

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

В алгоритме одиночного обхода

Я собираюсь рассматривать положительные целые и отрицательные целые во входных данных отдельно. Вы хотите сохранить работающий продукт положительных целых чисел, бегущий продукт отрицательных целых чисел и наибольшее отрицательное целое число (ie. Отрицательное целое число с наименьшим абсолютным значением), найденное до сих пор. Давайте проигнорируем крайние случаи, когда окончательный ответ <= 0. Это может быть легко обработано. </p>

//Initialization
int [] nums // Input
int posProduct = 1;
int negProduct = 1;
int smallestNeg = 1;

//Input Traversal
for (int i : nums) {
  if ( i == 0 ) {
    // ignore
  } else if ( i < 0 ) {
    if (smallestNeg == 1) {
      smallestNeg = i;
    } else if ( i > smallestNeg ) {
      negProduct *= smallestNeg; //Integrate the old smallest into the running product
      smallestNeg = i;           // i is the new smallest
    } else {
      negProduct *= i;
    }
  } else {
    // i is strictly positive
    posProduct *= i;
  }
}

//Result Computation
int result = posProduct;
if ( negProduct < 0 ) {
  // The running product of negative number numbers is negative
  // We use the smallestNeg to turn it back up to a positive product
  result *= smallestNeg;
  result *= negProduct;
} else {
  result *= negProduct
}

edit: В рекурсивном обходе

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

public class RecursiveSolver {
  public static int findMaxProduct (int [] nums) {
    return recursiveArrayTraversal(1, 1, 1, nums, 0); 
  }

  private static int recursiveArrayTraversal(int posProduct, int negProduct, 
      int smallestNeg, int [] nums, int index) {
    if (index == nums.length) {
      // End of the recursion, we traversed the whole array
      posProduct *= negProduct;
      if (posProduct < 0) {
        posProduct *= smallestNeg;
      }
      return posProduct;
    }

    // Processing the "index" element of the array
    int i = nums[index];
    if ( i == 0 ) {
      // ignore
    } else if ( i < 0 ) {
      if (smallestNeg == 1) {
        smallestNeg = i;
      } else if ( i > smallestNeg ) {
        negProduct *= smallestNeg; 
        smallestNeg = i;
      } else {
        negProduct *= i;
      }
    } else {
      // i is strictly positive
      posProduct *= i;
    }

    //Recursive call here! 
    //Notice the index+1 for the index parameter which carries the progress 
    //in the array traversal
    return recursiveArrayTraversal(posProduct, negProduct, 
      smallestNeg, nums, index+1);
  }
}

Answer 3

Сначала разбивайте массив в подзадачах, всегда находя 0 в списке:

 1 -2  4 -1  8  0  4  1  0 -3 -4  0  1  3 -5
|_____________|   |____|   |____|   |_______|
       p1           p2       p3         p4 

Затем для каждой задачи pi подсчитайте, сколько там отрицательных чисел.

Если pi имеет четное число негативов (или вообще не имеет негативов), ответ pi является произведением всех его элементов.

Если pi имеет только 1 отрицательное число (скажем, n), ответ будет максимальным между произведением всех элементов справа n и произведением всех элементов слева n.

Если pi имеет нечетное число (больше, чем 1) отрицательных чисел, вызовите индекс самого левого отрицательного числа l и индекс самого правого отрицательного числа r. Предположим, что pi имеет n элементов, ответ будет:

max(
    pi[  0  ] * pi[  1  ] * ... * pi[r - 1],
    pi[l + 1] * pi[l + 2] * ... * pi[  n  ]
)

Зная это, легко написать рекурсию для каждого шага решения этой проблемы: рекурсия для разделения задач по нулям. другой - для подсчета негативов, другой - для поиска ответов, в O (n).

Answer 4

Это мое решение - оставить его открытым для оптимизации и определения времени выполнения. Это универсальное решение, которое находит продукты всех комбинаций целых чисел в списке. Конечно, есть решение O (n), но я также представляю это решение.

import java.util.ArrayList;
import java.util.List;

public class MaxProd {

    int[] input = {1, 2, 3};

    // int[] input = {-2, -1, 1, 2, 3};

    public static void main(String[] args) {
        MaxProd m = new MaxProd();
        List<Integer> ll =  m.max(0);
        for (int i : ll) {
            System.out.println(i);
        }
        ll.sort((x,y) -> Integer.compare(x, y));
        System.out.println("The max: " + ll.get(ll.size() -1 ));

    }

    private List<Integer> max(int index) {
        if (index < input.length){
            List<Integer> l = new ArrayList<>();
            List<Integer> retList = max(index + 1);

            for (int j : retList){
                l.add(input[index] * j);
            }
            l.add(input[index]);
            l.addAll(retList);
            return l;
        }
        else return new ArrayList<>();

    }
}

он печатает:

6
2
3
1
6
2
3
The max: 6

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

Answer 5

Линейная версия

        List<Integer> vals = new ArrayList<>(List.of(5,1,-2,1,2,3,-4,-1));

        int prod = 0;
        int min = 1;
        for (int v : vals) {
            if (v == 0) {
                // ignore zero values
                continue;
            }
            if (prod == 0) {
                prod = 1;
            }
            prod *= v;
            // compute min to be the largest negative value in the list.
            if (v < 0 && min < Math.abs(v)) {
                min = v;
            }
        }
        if (prod < 0) {
            prod /= min;
        }

        System.out.println("Maximum product = " + prod);
    }

Рекурсивная версия

        int prod = prod(vals, new int[] {0} , vals.size());
        System.out.println("Maximum product = " + prod);

    public static int prod(List<Integer> vals, int[]min, int size) {
        int prod = 0;
        if(vals.size() > 0) {
            int t = vals.get(0);
             if (t < 0 && min[0] < Math.abs(t)) {
                    min[0] = t;
             }
             prod = prod(vals.subList(1,vals.size()), min, vals.size());
        }
        if (vals.isEmpty() || vals.get(0) == 0) {
            return prod;
        }

        if (prod == 0) {
           prod = 1;
        }
        prod *= t;

        if (vals.size() == size && prod < 0) {
            prod/=min[0];
        }
        return prod;    
    }