Javascript
 Computer >> コンピューター >  >> プログラミング >> Javascript

Kadaneのアルゴリズムを使用してJavaScriptでサブアレイの最大合計を見つける

問題

最初で唯一の引数として、整数の配列（正と負の両方）arrを受け取るJavaScript関数を作成する必要があります。

この関数は、線形時間でサブアレイの最大合計を返す必要があります

任意のインデックスiでのlocal_maximumは、arr [i]の最大値であり、インデックスi-1でのarr[i]とlocal_maximumの合計です。

これは、lineartimeで配列内の最大サブ配列合計を見つけるために適用するものです。

たとえば、関数への入力が-

の場合

入力 

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

出力 

const output = 6;

出力の説明

最大合計のサブアレイは-

であるため 
[4, -1, 2, 1]

例

以下はコードです-

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
   let currentSum = 0
   let maxSum = 0

   for (let elem of arr) {
      const nextSum = currentSum + elem
      maxSum = Math.max(maxSum, nextSum)
      currentSum = Math.max(nextSum, 0)
   }

   return maxSum
};
console.log(maxSequence(arr));

出力

6

  1. C ++のプレフィックス合計を使用したO（n）の最大サブ配列合計

    問題の説明 正の整数と負の整数の配列が与えられた場合、その配列の最大サブ配列の合計を求めます 例 入力配列が− {-12、-5、4、-1、-7、1、8、-3}の場合、出力は9 アルゴリズム 入力配列のプレフィックス合計を計算します。 Initialize− min_prefix_sum =0、res =-infinite i=0からnまでのループを維持します。 （nは入力配列のサイズです。） cand =prefix_sum [i] – mini キャンドの場合 がres（これまでのサブアレイの最大合計）より大きい場合は、resをcandで更新します。

  2. Kadaneのアルゴリズムを使用して最大サブアレイ問題を解決するPythonプログラム

    Kadaneのアルゴリズムを使用して最大のサブ配列を見つける必要がある場合、サブ配列の最大値を見つけるのに役立つメソッドが定義されます。イテレータは、最大サブ配列を追跡するために使用されます。 以下は同じのデモンストレーションです- 例 def find_max_sub_array(my_list, beg, end):    max_end_at_i = max_seen_till_now = my_list[beg]    max_left_at_i = max_left_till_now = beg    max_right_