Javaでの最大サブアレイ問題

投稿日: 2022-10-27 2022-10-27
タグ: Algorithms, Java Array

1. 概要

最大サブ配列の問題は、任意の配列で合計が最大の一連の連続する要素を見つけるタスクです。

たとえば、以下の配列では、強調表示されたサブ配列の合計は最大です（6）：

このチュートリアルでは、配列で最大のサブ配列を見つけるための2つのソリューションを見ていきます。そのうちの1つは、 O（n）時間と空間の複雑さを使用して設計します。

2. ブルートフォースアルゴリズム

ブルートフォースは、問題を解決するための反復的なアプローチです。ほとんどの場合、このソリューションでは、データ構造に対して何度も反復する必要があります。次のいくつかのセクションでは、このアプローチを適用して、最大サブアレイの問題を解決します。

2.1. アプローチ

一般的に、頭に浮かぶ最初の解決策は、考えられるすべてのサブ配列の合計を計算し、合計が最大のサブ配列を返すことです。

まず、インデックス0で始まるすべてのサブアレイの合計を計算します。同様に、は、0からn-1 までのすべてのインデックスで始まるすべてのサブ配列を検索します。ここで、nは配列の長さです。

したがって、インデックス 0 から開始し、反復の現在の合計にすべての要素を追加します。また、これまでに見られた最大合計を追跡します。この反復は、上の画像の左側に示されています。

画像の右側には、インデックス3で始まる反復が表示されています。この画像の最後の部分には、インデックス3と6の合計が最大のサブアレイがあります。

ただし、私たちのアルゴリズムは、0からn-1までのインデックスで始まるすべてのサブアレイを引き続き検索します。

2.2. 実装

Javaでこのソリューションを実装する方法を見てみましょう。

public int maxSubArray(int[] nums) {
 
    int n = nums.length;
    int maximumSubArraySum = Integer.MIN_VALUE;
    int start = 0;
    int end = 0;
 
    for (int left = 0; left < n; left++) {
 
        int runningWindowSum = 0;
 
        for (int right = left; right < n; right++) {
            runningWindowSum += nums[right];
 
            if (runningWindowSum > maximumSubArraySum) {
                maximumSubArraySum = runningWindowSum;
                start = left;
                end = right;
            }
        }
    }
    logger.info("Found Maximum Subarray between {} and {}", start, end);
    return maximumSubArraySum;
}

予想どおり、現在の合計が前の最大合計よりも大きい場合は、maximumSubArraySumを更新します。特に、次に、このサブアレイのインデックス位置を見つけるために開始と終了も更新します。

2.3. 複雑

一般的に言えば、ブルートフォースソリューションは、考えられるすべてのソリューションを取得するために、アレイを何度も繰り返します。これは、このソリューションにかかる時間が、配列内の要素の数に比例して増加することを意味します。これは、小さいサイズのアレイでは問題にならない場合があります。 しかし、アレイのサイズが大きくなるにつれて、このソリューションは効率的ではありません。

コードを調べると、2つのネストされたforループがあることもわかります。 したがって、このアルゴリズムの時間計算量はO（n2）であると結論付けることができます。

後のセクションでは、動的計画法を使用して、 O（n）の複雑さでこの問題を解決します。

3. 動的計画法

動的計画法は、問題をより小さなサブ問題に分割することによって問題を解決します。これは、分割統治アルゴリズムの解決手法と非常によく似ています。ただし、主な違いは、動的計画法がサブ問題を1回だけ解決することです。

次に、このサブ問題の結果を保存し、後でこの結果を再利用して他の関連するサブ問題を解決します。 このプロセスはメモ化として知られています。

3.1. カダネのアルゴリズム

Kadaneのアルゴリズムは、最大サブアレイ問題に対する一般的なソリューションであり、このソリューションは動的計画法に基づいています。

動的計画法の問題を解決する上で最も重要な課題は、最適なサブ問題を見つけることです。

3.2. アプローチ

この問題を別の方法で理解しましょう。

上の画像では、最大のサブ配列が最後のインデックス位置で終了していると想定しています。したがって、サブアレイの最大合計は次のようになります。

maximumSubArraySum = max_so_far + arr[n-1]

max_so_farは、インデックスn-2で終了するサブアレイの最大合計です。これは上の画像にも示されています。

これで、この仮定を配列内の任意のインデックスに適用できます。たとえば、n-2で終わるサブアレイの最大合計は次のように計算できます。

maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]

したがって、次のように結論付けることができます。

maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]

ここで、配列内のすべての要素はサイズ1の特別なサブ配列であるため、要素が最大合計自体よりも大きいかどうかも確認する必要があります。

maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])

これらの方程式を見ると、配列のすべてのインデックスで最大のサブ配列の合計を見つける必要があることがわかります。したがって、問題をnサブ問題に分割しました。配列を1回だけ繰り返すことで、すべてのインデックスで最大の合計を見つけることができます。

強調表示された要素は、反復の現在の要素を示しています。すべてのインデックスで、前に導出した式を適用して、max_ending_hereの値を計算します。これは、サブアレイに現在の要素を含めるか、このインデックスから新しいサブアレイを開始するかを識別するのに役立ちます。

別の変数max_so_farは、反復中に検出されたサブアレイの最大合計を格納するために使用されます。最後のインデックスを反復処理すると、max_so_farは最大サブアレイの合計を格納します。

3.3. 実装

繰り返しになりますが、上記のアプローチに従って、JavaでKadaneアルゴリズムを実装する方法を見てみましょう。

public int maxSubArraySum(int[] arr) {
 
    int size = arr.length;
    int start = 0;
    int end = 0;
 
    int maxSoFar = arr[0], maxEndingHere = arr[0];
 
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxEndingHere + arr[i]) {
            start = i;
            maxEndingHere = arr[i];
        } else
            maxEndingHere = maxEndingHere + arr[i];
 
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere;
            end = i;
        }
    }
    logger.info("Found Maximum Subarray between {} and {}", Math.min(start, end), end);
    return maxSoFar;
}

ここでは、startとendを更新して、最大のサブアレイインデックスを見つけました。

最大サブアレイの開始インデックスとして、 startの代わりにMath.min（start、end）を使用することに注意してください。これは、配列に負の数のみが含まれている場合、最大のサブ配列が最大の要素自体になるためです。この場合、 if（arr [i]> maxEndingHere + arr [i]）は常にtrueになります。つまり、startの値がend。の値よりも大きくなっています。

3.4. 複雑

配列を1回繰り返すだけでよいため、このアルゴリズムの時間計算量はO（n）です。

ご覧のとおり、このソリューションにかかる時間は、配列内の要素の数に比例して増加します。したがって、前のセクションで説明したブルートフォースアプローチよりも効率的です。

4. 結論

このクイックチュートリアルでは、最大サブアレイの問題を解決する2つの方法について説明しました。

最初に、ブルートフォースアプローチを検討し、この反復ソリューションが2次時間になることを確認しました。その後、Kadaneアルゴリズムについて説明し、動的計画法を使用して線形時間で問題を解決しました。

いつものように、記事の完全なソースコードは、GitHubでから入手できます。

getdocs

13036