Find maximum product using recursion

There's a question I saw and I'm wondering if it's possible to solve it using recursion. It goes as follow:

Write an algorithm that, when given an array of input, finds the maximum product from those inputs. For example:

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)

I'm trying to find a way of using recursion to solve it, but the algorithm I tried doesn't work. My algorithm, written in Java is as follow

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;
    
}

The problem with this algorithm is that it doesn't work well if there's an even number of negative numbers. For example, if nums[0]=-2, nums[1]=-1 and nums[2]=1, then multiply(nums, 1) will always return 1 instead of -1, and thus it will always see 1 as bigger than 1*-2 at multiply(nums, 0). I'm not sure how to solve this problem, however. Is there any way of solving this using recursion or dynamic programming?

What is the maximum product of integers?

To obtain the maximum sum, you will want to multiply all the positive integers with the product of the largest negative integers, with the number of negative integers included in the product being even to obtain a positive final result.

In an algorithm for a single traversal

I am going to treat the positive integers and the negative integers in the input separately. You will want to keep a running product of positive integers, a running product of negative integers and the largest negative integer (ie. the negative integer with the smallest absolute value) found so far.
Let us ignore the edge cases where the final answer is <= 0. That can be handled easily.

//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: In a recursive traversal

I personally find that writing the array traversal in a recursive manner to be clumsy but it can be done.
For the beauty of the exercise and to actually answer the question of the OP, here is how I would do it.

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);
  }
}

If there is only one non-zero element in the array, and it happens to be a negative number, then then answer is either 0, if there is a 0 present in the input, or if the array contains only that single negative element, the answer is that element itself.

In all other cases, the final answer is going to be positive.

We first make a linear scan to find the number of negative integers. If this number is even, then the answer is the product of all the non-zero elements. If there are an odd number of negative elements, we need to leave out one negative element from the answer, so that the answer is positive. As we want the maximum possible answer, the number we want to leave out should have as small an absolute value as possible. So among all the negative numbers, find the one with the minimum absolute value, and find the product of the remaining non-zero elements, which should be the answer.

All this requires only two linear scans of the array, and hence runs in O(n) time.

Linear version

	    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);
	}

Recursive version

		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;	
	}

</details>



# 答案4
**得分**: 0

以下是翻译好的内容：

这是我的解决方案 - 为了优化和计算运行时留下了空间。这是一个通用的解决方案，可以找到列表中所有整数的**所有组合**的乘积。当然，存在一个O(n)的解决方案，但我也提供这个解决方案。

```java
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("最大值: " + 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
最大值: 6

如果要求是有限制的（如本例），那么可以在不生成所有组合的情况下得到一个线性解决方案。此外，我在最后进行了排序。注意：你可以轻松地通过一次遍历返回的列表来找到最大乘积，正如其他答案中指定的那样。

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

答案5

得分: 0

首先，在列表中每次找到一个 0 时，将数组分割成子问题：

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

然后，对于每个问题 pi，计算其中有多少个负数。

如果 pi 中有偶数个负数（或者根本没有负数），则 pi 的答案是其所有元素的乘积。

如果 pi 中只有一个负数（记为 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)。

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

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