Kadane Algorithim

Kadane-Algorithim

これは、有名なダイナミックプログラミングアルゴカダンのアルゴリチムの1つに対するJavaScriptソリューションです。

問題ステートメント

n要素の配列a = {a1、a2、}が与えられた場合、aの最大可能な合計を見つけます

隣接するサブアレイは、非連続的な（必ずしも連続しているわけではない）サブアレイ。
空のサブアレイ/サブシーケンスを考慮しないでください。

ベン・ライトによるこのYouTubeビデオは、1-Dシーケンスでの最大サブアレイについてKadaneアルゴリズムを理解するのに役立つかもしれません。

入力形式

入力の最初の行には、整数Tがあります。Tケースが続きます。各テストケースは、整数Nから始まります。次の行では、n整数はアレイAの要素を表します。

制約：

1≤t≤10
1≤n≤105
-104≤ai≤104

あなたが考慮するサブアレイとサブシーケンスには、少なくとも1つの要素が必要です。

出力形式

2つのスペース分離された整数、最大の連続的で非連続したサブアレイを示す整数。少なくとも1つの整数を選択して、サブアレイに入れる必要があります（これは、すべての要素が負の場合に必要になる場合があります）。

サンプル入力

2
4
1 2 3 4
6
2 -1 2 3 4 -5

サンプル出力

10 10
10 11

説明

最初のケースでは、隣接する要素と非紛争要素の両方の最大合計は、すべての要素の合計です（すべてが正です）。

2番目のケースでは、[2 -1 2 3 4] - >これは、最大合計で隣接するサブアレイを形成します。必要でない要素のグループの最大合計については、すべてのポジティブな要素を追加するだけです。