7

しばらく前に面接で質問されたのですが、答えがありませんでした。どうやらそれを解決するための「非常に効率的な」アルゴリズムがあるようです。

質問: ランダムな正と負の数の配列が与えられた場合、合計が最大になる連続サブセットを見つけます。

例：

[1, -7, 4, 5, -1, 5]

ここでの最良のサブセットは{4, 5, -1, 5}

力ずくの方法以外に解決策は思いつきません。効率の良い方法とは？

4

5 に答える 5

4

これまでのリスト要素のローカル合計を追跡しながら、リストを反復処理します。
現地の合計がこれまでで最高の合計である場合は、それを記録します。
ローカル合計が 0 以下になった場合は、リセットして次の要素から再開します。

仮説

現在のサブセットの合計がゼロより大きい場合、将来のサブセットの合計に寄与するため、それを保持します。一方、現在のサブセットの合計がゼロ以下の場合、将来のサブセットの合計には寄与しません。したがって、それを捨てて、新しいサブセットの合計で新たに始めます。次に、現在のサブセットの合計が以前に遭遇したサブセットの合計よりも大きい場合を追跡するだけの問題です。

疑似コード

パラメータ内はlistlength の配列ですN。結果は と に格納されbest_startますbest_end。

best_sum = -MAX
best_start = best_end = -1
local_start = local_sum = 0

for i from 0 to N-1 {

    local_sum = local_sum + list[i]

    if local_sum > best_sum {
        best_sum = local_sum
        best_start = local_start
        best_end = i
    }

    if local_sum <= 0 {
        local_sum = 0
        local_start = i+1
    }

}
于 2012-08-29T05:54:12.973 に答える
2

リストを累積合計のリストに変換します[1,-7,4,5,-1,5] to [1, -6, -2, -3, 2]。次に、累積合計のリストをウォークスルーし、これまでの最小値と、現在の値として表示される値と現在の最小値との最大の差を保存します。ここから手に入れた

于 2012-08-28T19:13:05.237 に答える
1

ヒントを含むCLRSからこの質問に答えることができます。

次のアイデアを使用して、最大部分配列問題の非再帰的線形時間アルゴリズムを開発します。

配列の左端から開始し、これまでに見た最大のサブ配列を追跡しながら、右に向かって進みます。

の最大部分配列がわかれば、答えを拡張して、次の観測を使用してA[1..j]index で終わる最大部分配列を見つけます。j+1

の最大サブ配列A[1..j+1]は、 の最大サブ配列A[1..j]またはサブ配列 のいずれA[i..j+1]か1 <= i <= j + 1です。

A[i..j+1]index で終わる最大部分配列を知ることに基づいて、定数時間でフォームの最大部分配列を決定しますj。

max-sum = A[1]
current-sum = A[1]
left = right = 1
current-left = current-right = 1
for j = 2 to n
    if A[j] > current-sum + A[j]
        current-sum = A[j]
        current-left = current-right = j
    else
        current-sum += A[j]
        current-right = j
    if current-sum > max-sum
        max-sum = current-sum
        left = current-left
        right = current-right
return (max-sum, left, right)
于 2012-08-28T19:38:22.070 に答える
1

残念ながら、Java にはタプルの戻り値の型がありません。そのため、メソッドでインデックスと合計を出力する必要がありました。

public class Kadane {

    public static void main(String[] args) {
        int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
        findMaxSubArray(intArr);
    }

    public static void findMaxSubArray(int[] inputArray){

        int maxStartIndex=0;
        int maxEndIndex=0;
        int maxSum = Integer.MIN_VALUE; 

        int sum= 0;

        for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
            int eachArrayItem = inputArray[currentIndex];

            sum+=eachArrayItem;

            if( eachArrayItem > sum){
                maxStartIndex = currentIndex;    
                sum = eachArrayItem;      
            }
            if(sum>maxSum){
                maxSum = sum;
                maxEndIndex = currentIndex;
            }
        }

        System.out.println("Max sum         : "+maxSum);
        System.out.println("Max start index : "+maxStartIndex);
        System.out.println("Max end index   : "+maxEndIndex);
    }
}

そして、これが恥知らずなマーケティングです : これがどのように機能するかについてのスライドをまとめることができました

于 2012-08-29T11:44:10.133 に答える
1

線形時間で実行されるJavaクラスは次のとおりです

public class MaxSumOfContinousSubset {

    public static void main(String[] args) {
        System.out.println(maxSum(1, -7, 4, 5, -1, 5));
    }

    private static int maxSum (int... nums) {
        int maxsofar = 0;
        int maxhere = 0;
        for (int i = 0; i < nums.length; i++) {
            maxhere =  Math.max(maxhere + nums[i], 0);
            maxsofar = Math.max(maxhere, maxsofar);
        }
        return maxsofar;
    }
}
于 2012-09-30T13:04:22.170 に答える