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)。