オブジェクトを使用すると、キー付きの値のコレクションを保存できます。それはいいです。
しかし、多くの場合、1 番目、2 番目、3 番目の要素などがある、順序付けられたコレクションが必要であることがわかります。たとえば、ユーザー、商品、HTML 要素などのリストを保存するには、これが必要です。
ここでオブジェクトを使用するのは不便です。オブジェクトには要素の順序を管理するメソッドが提供されていないからです。既存のプロパティの「間」に新しいプロパティを挿入することはできません。オブジェクトはそのような用途を意図したものではありません。
順序付けされたコレクションを格納するために、 Array
という名前の特別なデータ構造が存在します。
空の配列を作成するには 2 つの構文があります。
arr = 新しい Array(); にします。 arr = []; とします。
ほとんどの場合、2 番目の構文が使用されます。括弧内に初期要素を指定できます。
果物 = ["リンゴ"、"オレンジ"、"プラム"];
配列要素には 0 から始まる番号が付けられます。
要素は角括弧内の番号で取得できます。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; アラート( フルーツ[0] ); // りんご アラート( フルーツ[1] ); // オレンジ アラート( フルーツ[2] ); // プラム
要素を置き換えることができます。
果物[2] = '梨'; // 現在 ["Apple"、"Orange"、"Pear"]
…または、新しいものを配列に追加します。
果物[3] = 'レモン'; // 現在 ["リンゴ"、"オレンジ"、"梨"、"レモン"]
配列内の要素の合計数がそのlength
なります。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; アラート(fruits.length); // 3
また、 alert
使用して配列全体を表示することもできます。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; アラート(果物); // アップル、オレンジ、プラム
配列には、任意の型の要素を格納できます。
例えば:
// 値の組み合わせ let arr = [ 'Apple', { name: 'John' }, true, function() {alert('hello'); } ]; // インデックス 1 のオブジェクトを取得し、その名前を表示します アラート( arr[1].name ); // ジョン // インデックス 3 の関数を取得して実行します arr[3](); // こんにちは
末尾のカンマ
配列は、オブジェクトと同様に、カンマで終わる場合があります。
果物を = [ "りんご"、 "オレンジ"、 "梅"、 ];
「末尾のカンマ」スタイルを使用すると、すべての行が同じになるため、項目の挿入/削除が簡単になります。
最近の追加
これは言語に最近追加されたものです。 古いブラウザにはポリフィルが必要な場合があります。
配列の最後の要素が必要だとします。
一部のプログラミング言語では、 fruits[-1]
のように、同じ目的で負のインデックスを使用できます。
ただし、JavaScript では機能しません。角括弧内のインデックスは文字通りに扱われるため、結果はundefined
になります。
最後の要素のインデックスを明示的に計算して、それにアクセスできます ( fruits[fruits.length - 1]
。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; alert(fruits[fruits.length-1]); // プラム
ちょっと面倒ですね。変数名を 2 回記述する必要があります。
幸いなことに、 fruits.at(-1)
という短い構文があります。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; // フルーツと同じ[fruits.length-1] アラート( フルーツ.at(-1) ); // プラム
言い換えると、 arr.at(i)
:
i >= 0
の場合、 arr[i]
とまったく同じです。
i
が負の値の場合、配列の最後からステップバックします。
キューは、配列の最も一般的な用途の 1 つです。コンピューター サイエンスでは、これは 2 つの操作をサポートする要素の順序付けされたコレクションを意味します。
push
要素を末尾に追加します。
shift
先頭から要素を取得し、2 番目の要素が 1 番目になるようにキューを進めます。
配列は両方の操作をサポートします。
実際にはそれが非常に頻繁に必要になります。たとえば、画面上に表示する必要があるメッセージのキューなどです。
配列にはもう 1 つの使用例があります。スタックという名前のデータ構造です。
次の 2 つの操作をサポートします。
push
最後に要素を追加します。
pop
末尾から要素を取得します。
したがって、新しい要素は常に「最後」から追加または取得されます。
スタックは通常、カードのパックとして示されます。新しいカードは一番上に追加されるか、一番上から取り出されます。
スタックの場合、最後にプッシュされたアイテムが最初に受信されます。これは、LIFO (Last-In-First-Out) 原則とも呼ばれます。キューには FIFO (先入れ先出し) があります。
JavaScript の配列は、キューとしてもスタックとしても機能します。これらを使用すると、先頭または末尾の両方に要素を追加または削除できます。
コンピューター サイエンスでは、これを可能にするデータ構造を deque と呼びます。
配列の末尾を操作するメソッド:
pop
配列の最後の要素を抽出して返します。
果物 = ["リンゴ"、"オレンジ"、"梨"]; アラート( フルーツ.ポップ() ); // 「Pear」を削除して警告します アラート(果物); // アップル、オレンジ
fruits.pop()
とfruits.at(-1)
はどちらも配列の最後の要素を返しますが、 fruits.pop()
は配列を削除して変更します。
push
要素を配列の末尾に追加します。
果物 = ["リンゴ", "オレンジ"]; フルーツ.push("梨"); アラート(果物); // リンゴ、オレンジ、洋ナシ
fruits.push(...)
の呼び出しはfruits[fruits.length] = ...
と同じです。
配列の先頭で機能するメソッド:
shift
配列の最初の要素を抽出して返します。
果物 = ["リンゴ"、"オレンジ"、"梨"]; アラート( フルーツ.シフト() ); // Apple を削除して警告します アラート(果物); // オレンジ、洋ナシ
unshift
要素を配列の先頭に追加します。
果物 = ["オレンジ", "洋ナシ"]; フルーツ.unshift('アップル'); アラート(果物); // リンゴ、オレンジ、洋ナシ
push
メソッドとunshift
メソッドでは、複数の要素を一度に追加できます。
果物 = ["リンゴ"]; フルーツ.push("オレンジ", "ピーチ"); Fruits.unshift("パイナップル", "レモン"); // ["パイナップル"、"レモン"、"リンゴ"、"オレンジ"、"ピーチ"] アラート(果物);
配列は特別な種類のオブジェクトです。プロパティarr[0]
アクセスするために使用される角括弧は、実際にはオブジェクト構文から来ています。これは本質的にobj[key]
と同じで、 arr
がオブジェクトであり、数値がキーとして使用されます。
これらはオブジェクトを拡張し、順序付けられたデータのコレクションとlength
プロパティを操作するための特別なメソッドを提供します。しかし、本質的には依然としてオブジェクトです。
JavaScript には基本的なデータ型が 8 つしかないことに注意してください (詳細については、「データ型」の章を参照してください)。配列はオブジェクトなので、オブジェクトのように動作します。
たとえば、参照によってコピーされます。
果物 = [「バナナ」] にしましょう arr = 果物とします。 // 参照によるコピー (2 つの変数が同じ配列を参照する) alert( arr === フルーツ ); // 真実 arr.push("梨"); // 配列を参照によって変更します アラート(果物); // バナナ、梨 - 現在 2 アイテム
…しかし、配列を本当に特別なものにしているのは、その内部表現です。この章の図に示されているように、エンジンは要素を連続したメモリ領域に次々と保存しようとします。また、配列を高速に動作させるための他の最適化も行われています。
しかし、「順序付きコレクション」のように配列を扱うのをやめて、通常のオブジェクトであるかのように配列を扱い始めると、それらはすべて壊れてしまいます。
たとえば、技術的には次のことが可能です。
果物を = [] にします。 // 配列を作成する 果物[99999] = 5; // その長さをはるかに超えるインデックスを持つプロパティを割り当てます フルーツ.年齢 = 25; // 任意の名前でプロパティを作成します
配列はそのベースがオブジェクトであるため、それが可能です。任意のプロパティを追加できます。
ただし、エンジンは、配列を通常のオブジェクトと同様に操作していることを認識します。配列固有の最適化はそのような場合には適していないためオフになり、その利点は失われます。
配列を悪用する方法は次のとおりです。
arr.test = 5
のような非数値プロパティを追加します。
arr[0]
を追加し、次にarr[1000]
します (その間には何も追加しません)。
arr[1000]
、 arr[999]
などのように、逆の順序で配列を埋めます。
配列は、順序付けされたデータを処理するための特別な構造であると考えてください。彼らはそのための特別なメソッドを提供します。配列は、連続した順序付けされたデータを処理できるように JavaScript エンジン内で慎重に調整されています。このように使用してください。また、任意のキーが必要な場合は、実際には通常のオブジェクト{}
が必要である可能性が高くなります。
メソッドのpush/pop
高速に実行されますが、 shift/unshift
は低速です。
配列の先頭で作業するよりも配列の末尾で作業するほうが速いのはなぜですか?実行中に何が起こるかを見てみましょう。
フルーツ.シフト(); // 先頭から1要素を取り出します
インデックス0
の要素を取得して削除するだけでは十分ではありません。他の要素も同様に番号を付け直す必要があります。
shift
操作では次の 3 つのことを行う必要があります。
インデックス0
の要素を削除します。
すべての要素を左に移動し、インデックス1
から0
、 2
から1
などに番号を付け直します。
length
プロパティを更新します。
配列内の要素が多いほど、要素を移動する時間が長くなり、メモリ内操作も多くなります。
同様のことがunshift
でも起こります。配列の先頭に要素を追加するには、まず既存の要素を右に移動して、インデックスを増やす必要があります。
push/pop
とは何ですか?何も動かす必要はありません。末尾から要素を抽出するために、 pop
メソッドはインデックスをクリーンアップし、 length
短縮します。
pop
操作のアクション:
フルーツ.ポップ(); // 末尾から 1 要素を取り出します
他の要素はインデックスを保持しているため、 pop
メソッドは何も移動する必要がありません。だからこそ猛烈に速いのです。
push
方式でも同様です。
配列項目を循環させる最も古い方法の 1 つは、インデックスに対するfor
ループです。
let arr = ["リンゴ", "オレンジ", "梨"]; for (let i = 0; i < arr.length; i++) { アラート( arr[i] ); }
ただし、配列の場合は、別の形式のループfor..of
があります。
果物 = ["リンゴ"、"オレンジ"、"プラム"]; // 配列要素を反復処理します for (フルーツをフルーツにしましょう) { アラート(フルーツ); }
for..of
現在の要素の番号にはアクセスせず、その値のみにアクセスしますが、ほとんどの場合はそれで十分です。そしてそれはより短いです。
技術的には、配列はオブジェクトであるため、 for..in
使用することもできます。
let arr = ["リンゴ", "オレンジ", "梨"]; for (arr にキーを入れます) { アラート( arr[キー] ); // リンゴ、オレンジ、洋ナシ }
しかし、それは実際には悪い考えです。それには潜在的な問題があります。
for..in
ループは、数値プロパティだけでなく、すべてのプロパティを反復処理します。
ブラウザや他の環境には、配列のように見える、いわゆる「配列のような」オブジェクトがあります。つまり、 length
とインデックスのプロパティを持っていますが、通常は必要のない他の数値以外のプロパティやメソッドも持っている可能性があります。ただし、 for..in
ループではそれらがリストされます。したがって、配列のようなオブジェクトを操作する必要がある場合、これらの「余分な」プロパティが問題になる可能性があります。
for..in
ループは配列ではなく汎用オブジェクトに対して最適化されているため、10 ~ 100 倍遅くなります。もちろん、それでも非常に速いです。高速化が重要になるのはボトルネックの場合だけかもしれません。しかし、それでも違いを認識しておく必要があります。
一般に、配列にfor..in
使用すべきではありません。
配列を変更すると、 length
プロパティが自動的に更新されます。正確に言うと、実際には配列内の値の数ではなく、最大の数値インデックスに 1 を加えたものになります。
たとえば、大きなインデックスを持つ 1 つの要素の長さは大きくなります。
果物を = [] にします。 果物[123] = "リンゴ"; アラート(fruits.length); // 124
通常、そのような配列は使用しないことに注意してください。
length
プロパティに関するもう 1 つの興味深い点は、書き込み可能であることです。
手動で増やしても、何も興味深いことは起こりません。しかし、それを減らすと、配列は切り詰められます。このプロセスは元に戻すことができません。例を次に示します。
arr = [1, 2, 3, 4, 5]; とします。 arr.length = 2; // 2要素に切り詰めます アラート(arr); // [1, 2] arr.length = 5; // 長さを戻す アラート( arr[3] ); // 未定義: 値は返されません
したがって、配列をクリアする最も簡単な方法は次のとおりです。 arr.length = 0;
。
配列を作成するにはもう 1 つの構文があります。
let arr = new Array("Apple", "Pear", "etc");
角括弧[]
は短いため、ほとんど使用されません。また、これには厄介な機能があります。
new Array
数値である単一の引数を指定して呼び出された場合、項目を持たずに指定された長さの配列が作成されます。
足を撃つ方法を見てみましょう。
arr = 新しい配列(2); // [2] の配列を作成しますか? アラート( arr[0] ); // 未定義!要素はありません。 アラート(arr.length); // 長さ 2
このような驚きを避けるために、実際に何をしているのかをよく理解していない限り、通常は角括弧を使用します。
配列には配列である項目を含めることができます。これを多次元配列に使用して、たとえば行列を保存できます。
行列 = [ [1、2、3]、 [4、5、6]、 [7、8、9] ]; アラート(行列[0][1]); // 2、最初の内部配列の 2 番目の値
配列には、要素のカンマ区切りリストを返すtoString
メソッドの独自の実装があります。
例えば:
arr = [1, 2, 3] とします。 アラート(arr); // 1、2、3 alert( String(arr) === '1,2,3' ); // 真実
また、これを試してみましょう:
アラート( [] + 1 ); // "1" アラート( [1] + 1 ); // 「11」 アラート( [1,2] + 1 ); // "1,21"
配列にはSymbol.toPrimitive
も実行可能なvalueOf
ありません。 toString
変換のみを実装するため、ここで[]
空の文字列になり、 [1]
は"1"
になり、 [1,2]
は"1,2"
になります。
バイナリ プラス"+"
演算子が文字列に何かを追加すると、それも文字列に変換されるため、次のステップは次のようになります。
アラート( "" + 1 ); // "1" アラート( "1" + 1 ); // 「11」 アラート( "1,2" + 1 ); // "1,21"
他のプログラミング言語とは異なり、JavaScript の配列は演算子==
と比較すべきではありません。
この演算子は配列に対して特別な処理を行わず、他のオブジェクトと同様に配列に対して機能します。
ルールを思い出してみましょう。
2 つのオブジェクトが等しい==
なのは、それらが同じオブジェクトへの参照である場合のみです。
==
の引数の 1 つがオブジェクトで、もう 1 つがプリミティブの場合、「オブジェクトからプリミティブへの変換」の章で説明されているように、オブジェクトはプリミティブに変換されます。
…ただし、 ==
相互に等価であり、それ以外には何も等しいnull
とundefined
除きます。
厳密な比較===
型を変換しないため、さらに単純です。
したがって、 ==
使用して配列を比較する場合、まったく同じ配列を参照する 2 つの変数を比較しない限り、それらは決して同じにはなりません。
例えば:
アラート( [] == [] ); // 間違い アラート( [0] == [0] ); // 間違い
これらの配列は技術的には異なるオブジェクトです。したがって、それらは平等ではありません。 ==
演算子は項目ごとの比較を行いません。
プリミティブと比較すると、一見奇妙な結果が得られる場合もあります。
アラート( 0 == [] ); // 真実 アラート('0' == [] ); // 間違い
ここでは、どちらの場合も、プリミティブと配列オブジェクトを比較します。したがって、配列[]
は比較のためにプリミティブに変換され、空の文字列''
になります。
次に、「型変換」の章で説明されているように、プリミティブを使用して比較プロセスが続行されます。
// [] が '' に変換された後 アラート( 0 == '' ); // true、'' は数値 0 に変換されるため アラート('0' == '' ); // false、型変換なし、異なる文字列
では、配列を比較するにはどうすればよいでしょうか?
それは簡単です。 ==
演算子を使用しないでください。代わりに、ループ内で項目ごとに比較するか、次の章で説明する反復方法を使用して比較します。
配列は特別な種類のオブジェクトで、順序付けされたデータ項目の保存と管理に適しています。
宣言:
// 角括弧 (通常) let arr = [item1, item2...]; // 新しい配列 (非常にまれ) let arr = new Array(item1, item2...);
new Array(number)
を呼び出すと、指定された長さの要素のない配列が作成されます。
length
プロパティは、配列の長さ、または正確には、その最後の数値インデックスに 1 を加えたものです。配列メソッドによって自動調整されます。
length
手動で短くすると、配列は切り詰められます。
要素を取得します。
arr[0]
のようにインデックスで要素を取得できます。
負のインデックスを許可するat(i)
メソッドを使用することもできます。 i
が負の値の場合、配列の最後からステップバックします。 i >= 0
の場合、 arr[i]
と同じように機能します。
次の操作で配列を両端キューとして使用できます。
push(...items)
items
最後に追加します。
pop()
末尾から要素を削除して返します。
shift()
先頭から要素を削除して返します。
unshift(...items)
items
先頭に追加します。
配列の要素をループするには:
for (let i=0; i<arr.length; i++)
– 最速で動作し、古いブラウザと互換性があります。
for (let item of arr)
– 項目のみの最新の構文、
for (let i in arr)
– 決して使用しないでください。
配列を比較する場合、 ==
演算子 (および>
、 <
など) は配列に対して特別な処理を行わないため、使用しないでください。彼らはそれらをオブジェクトとして扱いますが、それは私たちが通常望んでいることではありません。
代わりに、 for..of
ループを使用して配列を項目ごとに比較できます。
次の章「配列メソッド」では、配列の説明を続け、要素を追加、削除、抽出し、配列を並べ替えるメソッドをさらに学習します。
重要性: 3
このコードは何を示すのでしょうか?
let Fruits = ["リンゴ"、"ナシ"、"オレンジ"]; // 新しい値を「コピー」にプッシュします shoppingCart = 果物とします。 shoppingCart.push("バナナ"); // 果物には何が入っているの? アラート(fruits.length); //?
結果は4
です。
let Fruits = ["リンゴ"、"ナシ"、"オレンジ"]; shoppingCart = 果物とします。 shoppingCart.push("バナナ"); アラート(fruits.length); // 4
それは配列がオブジェクトだからです。したがって、 shoppingCart
とfruits
両方とも同じ配列への参照です。
重要度: 5
5 つの配列演算を試してみましょう。
項目「Jazz」と「Blues」を含む配列styles
を作成します。
最後に「Rock-n-Roll」を追加します。
中央の値を「Classics」に置き換えます。中間値を見つけるコードは、奇数の長さの配列に対して機能するはずです。
配列の最初の値を取り除いて表示します。
Rap
とReggae
配列の先頭に追加します。
プロセス内の配列:
ジャズ、ブルース ジャズ、ブルース、ロックンロール ジャズ、クラシック、ロックンロール クラシック、ロックンロール ラップ、レゲエ、クラシック、ロックンロール
let スタイル = ["ジャズ", "ブルース"]; スタイル.push("ロックンロール"); スタイル[Math.floor((styles.length - 1) / 2)] = "クラシック"; アラート(styles.shift() ); style.unshift("ラップ", "レゲエ");
重要度: 5
結果は何ですか?なぜ?
arr = ["a", "b"]; とします。 arr.push(関数() { アラート(これ); }); arr[2](); //?
arr[2]()
の呼び出しは、構文的には古き良きobj[method]()
であり、 obj
の役割にはarr
があり、 method
の役割には2
があります。
したがって、オブジェクト メソッドとして関数arr[2]
を呼び出します。当然のことながら、オブジェクトarr
参照するthis
を受け取り、配列を出力します。
arr = ["a", "b"]; とします。 arr.push(関数() { アラート(これ); }) arr[2](); // a,b,function(){...}
配列には 3 つの値があります。最初は 2 つと関数がありました。
重要度: 4
次の関数sumInput()
を作成します。
prompt
使用してユーザーに値を要求し、その値を配列に保存します。
ユーザーが数値以外の値または空の文字列を入力するか、「キャンセル」を押すと、質問が終了します。
配列項目の合計を計算して返します。
PS ゼロ0
は有効な数値です。ゼロで入力を停止しないでください。
デモを実行する
ソリューションの微妙ですが重要な詳細に注目してください。 value = +value
の後では、空の文字列 (停止記号) とゼロ (有効な数値) を区別できないため、 prompt
の直後にvalue
数値に変換しません。代わりに後で行います。
関数 sumInput() { 数値 = []; とします。 while (true) { let value =prompt("数字を教えてください?", 0); // キャンセルしたほうがいいでしょうか? if (値 === "" || 値 === null || !isFinite(value)) ブレーク; 数値.push(+値); } 合計 = 0 とします。 for (数値の数を指定します) { 合計 += 数値; } 合計を返します。 } アラート( sumInput() );
重要性: 2
入力は数値の配列です (例: arr = [1, -2, 3, 4, -9, 6]
。
タスクは、項目の合計が最大になるarr
の連続した部分配列を見つけることです。
その合計を返す関数getMaxSubSum(arr)
を作成します。
例えば:
getMaxSubSum([-1, 2, 3, -9]) == 5 (強調表示された項目の合計) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (すべてを取る)
すべての項目が負の場合は、何も取らない (部分配列が空である) ことを意味するため、合計はゼロになります。
getMaxSubSum([-1, -2, -3]) = 0
高速な解決策を考えてみてください。O(n 2 ) または可能であれば O(n) です。
テストを含むサンドボックスを開きます。
考えられるすべての部分合計を計算できます。
最も簡単な方法は、すべての要素を取得し、そこから始まるすべての部分配列の合計を計算することです。
たとえば、 [-1, 2, 3, -9, 11]
の場合:
// -1 から開始: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // 2から開始: 2 2+3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // 3 から開始: 3 3 + (-9) 3 + (-9) + 11 // -9 から開始 -9 -9 + 11 // 11から始まります 11
このコードは実際にはネストされたループです。配列要素に対する外部ループと、現在の要素から始まる内部カウントの積和です。
関数 getMaxSubSum(arr) { maxSum = 0 とします。 // 要素を取得しない場合はゼロが返されます for (let i = 0; i < arr.length; i++) { sumFixedStart = 0 とします。 for (let j = i; j < arr.length; j++) { sumFixedStart += arr[j]; maxSum = Math.max(maxSum, sumFixedStart); } } maxSum を返します。 } アラート( getMaxSubSum([-1, 2, 3, -9]) ); // 5 アラート( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 アラート( getMaxSubSum([-2, -1, 1, 2]) ); // 3 アラート( getMaxSubSum([1, 2, 3]) ); // 6 アラート( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
この解の時間計算量は O(n 2 ) です。つまり、配列サイズを 2 倍にすると、アルゴリズムは 4 倍長く動作します。
大きな配列 (1000、10000、またはそれ以上の項目) の場合、このようなアルゴリズムは深刻な遅延を引き起こす可能性があります。
配列を調べて、要素の現在の部分和を変数s
に保持してみましょう。ある時点でs
が負になった場合は、 s=0
を割り当てます。 s
ようなすべての の最大値が答えになります。
説明が曖昧すぎる場合は、十分に短いコードを参照してください。
関数 getMaxSubSum(arr) { maxSum = 0 とします。 部分合計 = 0 にします。 for (let item of arr) { // arr の各項目に対して 部分合計 += 項目; // それをpartialSumに追加します maxSum = Math.max(maxSum、partialSum); // 最大値を覚えておく if (部分的な合計 < 0) 部分的な合計 = 0; // 負の場合はゼロ } maxSum を返します。 } アラート( getMaxSubSum([-1, 2, 3, -9]) ); // 5 アラート( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 アラート( getMaxSubSum([-2, -1, 1, 2]) ); // 3 アラート( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 アラート( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([-1, -2, -3]) ); // 0
このアルゴリズムには 1 つの配列パスが必要なので、時間計算量は O(n) です。
アルゴリズムの詳細については、「最大部分配列問題」を参照してください。なぜそれが機能するのかがまだ明らかでない場合は、上記の例でアルゴリズムを追跡し、それがどのように機能するかを確認してください。それはどんな言葉よりも優れています。
サンドボックス内のテストを含むソリューションを開きます。