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)

时间和空间复杂度

上述代码的空间复杂度为O(1)，因为我们在代码中没有使用任何额外的空间。我们正在遍历数组一次，这意味着总共有N次迭代，因此上述代码的时间复杂度为O(N)。

结论

在这篇文章中，我们实现了一个用于最大乘积子数组的JavaScript程序。子数组是由数组的一部分组成，通过移除数组的前缀或后缀元素（或不移除）形成。我们实现了两种方法，空间复杂度均为O(1)，时间复杂度分别为O(N*N)和O(N)。