JavaScript 最大乘积子数组的程序

子数组是通过从数组中删除一些或没有前缀和删除给定数组的一些或没有后缀元素形成的数组的一部分。我们将尽力找到包含这些元素的子数组，并通过将它们全部相乘来获得最大值。我们将通过解释来实现代码。在本文中，我们将实现一个用于最大乘积子数组的JavaScript程序。

问题简介

在这个问题中，我们给出一个数组，并且我们必须从给定的数组中选择任意子数组，但问题是子数组的大小也无关紧要，重要的是子数组中所有元素的乘积必须是所有子数组中的最大值。

如果给定的数组只包含正数，那么结果总是可以是给定数组；如果存在任何零，则当前数组将被分割为许多以零为分界的子数组，并且在所有这些子数组中，位于边缘或在零之间的子数组是最大的。

现在，第三种情况，如果数组中还包含负数，那么问题是如果有两个或多个负数，那么我们将得到正的结果，否则在奇数个负数的情况下，我们将得到负的结果。

例如 −

情况1 − 所有的正数

Given array: 1 2 3 4 2 2 1 
Final answer: 96

情况2 − 所有非负数

Given array: 1 2 3 0 4 5 1 0 9 2 0 0 
Final answer: 20 by taking 4 5 1 as a subarray

在这里我们有三个分区：1 2 3，4 5 1 和 9 2，在所有这些中间的那个是最大的。

情况3 − 所有整数

Given array: -40 -2 0 1 5 -9 -8 -6 0 9 8 3

Final answer: 360 by taking the 1 5 -9 -8, there are other subarrays with some high values but are less as compared to this

方法

有两种方法可以运行该程序，即：第一种是朴素方法，在这种方法中，首先我们将找到给定数组的所有子数组，然后将它们的所有数字相乘以找到最大的乘积。让我们看一下它的代码 −

示例

// function to find the multiplication of the subarray
// with the largest result
function maxMulti(arr){
   var len = arr.length
   var ans = 0 // marking zero as the initial answer
   var cur = 1 // marking variable to get the current subarray multiplication

   // traversing over the array to get each subarray result
   for(var i = 0;i<len; i++) {
      cur = 1;
      for(var j = i; j<len ;j++){
         cur *= arr[j];
         if(ans < cur){
            ans = cur
         }
      }
   }
   console.log("The largest multiplication of subarray is: " + ans)
}

// definging the array's
arr1 = [1, 2, 3, 4, 2, 2, 1 ]
maxMulti(arr1)

// defining the second array
arr2 = [1, 2, 3, 0, 4, 5, 1, 0, 9, 2, 0, 0]
maxMulti(arr2)

// defining the third array
arr3 = [-40, -2, 0, 1, 5, -9, -8, -6, 0, 9, 8, 3]
maxMulti(arr3)

时间和空间复杂度

以上代码的时间复杂度为O(N*N)，其中N是数组的长度，以上代码的空间复杂度为O(1)。

以上代码的时间复杂度不好，可以更好地改进，为此我们将编写另一种方法来改进时间复杂度。

示例

在这个代码中，我们将使用分区和数论的概念，让我们先看看代码。

// function to find the multiplictaion of subarray
// with the largest result

function maxMulti(arr){
   var max_ending = 1;
   var min_ending = 1;
   var ans = 0;
   var temp= 0;
   var n = arr.length
   for(var i = 0; i < n; i++) {
      if (arr[i] > 0) {
         max_ending = max_ending * arr[i];
         if(1 < min_ending * arr[i]) {
            min_ending = 1
         }
         else
            min_ending = min_ending * arr[i]
         temp = 1;
      }
      else if (arr[i] == 0) {
         max_ending = 1;
         min_ending = 1;
      } else {
         var flag = max_ending;
         max_ending = min_ending * arr[i] > 1 ? min_ending * arr[i] : 1;
         min_ending = flag * arr[i];
      }

      // update max_so_far, if needed
      if (ans < max_ending)
      ans = max_ending;
   }
   if (temp == 0 && ans == 0){
      console.log("The largest multiplication of subarray is: " + 0)
   } else
   console.log("The largest multiplication of subarray is: " + ans)
}

// defining the array's
arr1 = [1, 2, 3, 4, 2, 2, 1 ]
maxMulti(arr1)

// defining the second array
arr2 = [1, 2, 3, 0, 4, 5, 1, 0, 9, 2, 0, 0]
maxMulti(arr2)

// defining the third array
arr3 = [-40, -2, 0, 1, 5, -9, -8, -6, 0, 9, 8, 3]
maxMulti(arr3)