algorithm - 合計が数 K で割り切れる部分配列を見つけます。部分配列は、すべての可能な部分配列の最大合計でなければなりません

Question

私はアルゴリズムの質問を練習してきましたが、これに出会いました。
(+ve と -ve の両方の) 数値の配列が与えられた場合、合計が任意の数 K で割り切れ、サブ配列がおそらく最大の合計になるように、連続したサブ配列を見つける必要があります。たとえば。
a={1,2,2,1,1,4,5,3}そしてk=5、k で割り切れる最大合計部分配列は
{2,2,1,1,4,5}, sum = 15
次のようになります。しかし、これは指数アルゴリズムになります。
編集:これを線形時間で解決することは可能ですか? 助けてください

Answer 1

この問題のキーワードは、prefix sum です。

それらを計算する擬似コードは次のようになります。

int prefix_sum[N];
prefix_sum[0] = array[0];
for (i = 1; i < n; i++)
    prefix_sum[i] = prefix_sum[i-1] + array[i];

接頭辞の合計が得られたので、残っているのはサブ配列を見つけることだけです。サブ配列の (前の) 最初のプレフィックス合計値を最後から減算するだけで、サブ配列の合計を見ることができます。

私たちが気にかけているプロパティは、和と K による割り算です。最大和部分配列を見つけるために、各要素を 1 回調べます。各要素を 1 回見ながら、次の 4 つのことを行います。

1. K: を法として前置和を割りますrem[i] = prefix_sum[i] % K;。このようにして、 の場合にのみサブ配列が有効であることがわかりましたrem[start_subarray] + rem[end_subarray] == K。しかし、サブ配列が割り切れるかどうかを確認するために使用するだけでなく、サブ配列を見つけるためにも使用できます (以下を参照)。

2. max_startサイズの配列を使用しますK。の剰余を計算するとき、prefix_sum[i] が の現在のインデックスの prefix_sum よりも大きい場合、prefix_sum[i]インデックスを に格納します。これで、O(1) で、プレフィックスの合計が最大で、残りが指定されたインデックスを検索できるようになりました。imax_start[rem[i]]max_start[rem[i]]

3. この要素について、array[i]を調べrem[i]て、残りが である最大の prefix_sum を持つ要素を検索しますK-rem[i]。これを行うと、a) K で割り切れ、b) (この要素で終わるすべての配列に対して) 最大の合計を持つ部分配列が得られますarray[i]。

4. この配列の合計が、現在見つかっている最大の配列よりも大きいかどうかを確認し、その場合は、この配列を新しいトップ スコアラーとして設定します。

適切なインデックスを探す必要があり、すべての例外ケース (何も見つからない場合など...) を処理する必要があるため、詳細は非常に複雑ですが、アルゴリズムのアイデアは理解できると思います。この実行時間は O(n) であり、接頭辞の合計のおかげで、負の数と正の数に対して機能するはずです。

Answer 2

このための分割統治アルゴリズムを書きました。

FindMaxSubarrayDivisible(array,start,end,maxStart,maxEnd,sum,k) が k で割り切れる最大連続部分配列を計算する関数である場合、次のようになります。

FindMaxSubarrayDivisible(array, start, end, out maxStart, out maxEnd, out sum, k)
    mid=(start+end)/2;
    FindMaxSubarrayDivisible(array, start, mid, out leftMaxStart, out leftMaxEnd, out leftSum, k)
    FindMaxSubarrayDivisible(array, mid, end, out rightMaxStart, out rightMaxEnd, out rightSum, k)
    FindMaxCrossingSubarrayDivisible(array, start, end, out crossMaxStart, out crossMaxEnd, out crossSum, k)
    Determine the max of the three above, if exists

FindMaxCrossingSubarrayDivisibleO(k) ストレージを使用して O(max(n,k)) 時間で実行できます。私の考えは、k 個の整数の配列を持つことです。ここで、各要素は、0 <= i < k である剰余 i の配列の右側の最大交差合計を格​​納します。配列の左側についても同じことを行い、O(k) 時間でマージします。k << n の場合、このアルゴリズムは O(n lg n) 時間です。

このために、次の C# コードを作成しました。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication3
{
    class Program
    {
        static int k;

        static void Main(string[] args)
        {
            k = 5;
            int maxStart;
            int maxEnd;
            int sum;

            int[] a = new int[] { };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { 1 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { 2,1 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { 2,3 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { 3,2,3,2 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { -5,10,15,-5 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { 1, 2, 2, 1, 1, 4, 5, 3 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);

            a = new int[] { -1,-2,-3,-4,-5 };
            f(a, 0, a.Length, out maxStart, out maxEnd, out sum);
            Console.WriteLine("{0},{1},{2}", maxStart, maxEnd, sum);
        }

        static void f(int[] a, int start, int end, out int maxStart, out int maxEnd, out int sum)
        {
            if (end - start < 0)
            {
                throw new ArgumentException();
            }
            else if (end - start == 0)
            {
                maxStart = start;
                maxEnd = end;
                sum = 0;
            }
            else if (end - start == 1)
            {
                if (a[start] % k == 0)
                {
                    maxStart = start;
                    maxEnd = end;
                    sum = a[start];
                }
                else
                {
                    maxStart = -1;
                    maxEnd = -1;
                    sum = 0;
                }
            }
            else
            {
                int leftMaxStart;
                int leftMaxEnd;
                int leftMaxSum;
                int rightMaxStart;
                int rightMaxEnd;
                int rightMaxSum;
                int mid = (start + end) / 2;
                f(a, start, mid, out leftMaxStart, out leftMaxEnd, out leftMaxSum);
                f(a, mid, end, out rightMaxStart, out rightMaxEnd, out rightMaxSum);

                int[] r = new int[k];
                int[] rightEnds = new int[k];   //right end index array
                for (int i = 0; i < k; ++i)
                {
                    rightEnds[i] = -1;
                }
                int midSum = a[mid - 1] + a[mid];
                int midRightSum = midSum;
                int mod = Math.Abs(midRightSum % k);
                if (midRightSum > r[mod] || rightEnds[mod] == -1)
                {
                    r[mod] = midRightSum;
                    rightEnds[mod] = mid + 1;
                }
                for (int i = mid + 1; i < end; ++i)
                {
                    midRightSum += a[i];
                    mod = Math.Abs(midRightSum % k);
                    if (midRightSum > r[mod] || rightEnds[mod] == -1)
                    {
                        r[mod] = midRightSum;
                        rightEnds[mod] = i + 1;
                    }
                }

                int[] l = new int[k];
                int[] leftStarts = new int[k];  //left end index array
                for (int i = 0; i < k; ++i)
                {
                    leftStarts[i] = -1;
                }
                int leftSum = 0;
                for (int i = mid - 2; i >= start; --i)
                {
                    leftSum += a[i];
                    mod = Math.Abs(leftSum % k);
                    if (leftSum > l[mod] || leftStarts[mod] == -1)
                    {
                        l[mod] = leftSum;
                        leftStarts[mod] = i;
                    }
                }

                int crossMaxSum = int.MinValue;
                int crossMaxStart = -1;
                int crossMaxEnd = -1;
                if (rightEnds[0] != -1)
                {
                    crossMaxSum = r[0];
                    crossMaxStart = mid - 1;
                    crossMaxEnd = rightEnds[0];
                    if (leftStarts[0] != -1)
                    {
                        int crossSum = l[0] + r[0];
                        if (crossSum > crossMaxSum)
                        {
                            crossMaxSum = crossSum;
                            crossMaxStart = leftStarts[0];
                            crossMaxEnd = rightEnds[0];
                        }
                    }
                }
                for (int i = 1; i < k; ++i)
                {
                    int crossSum = l[i] + r[k-i];
                    if (crossSum > crossMaxSum)
                    {
                        crossMaxSum = crossSum;
                        crossMaxStart = leftStarts[i];
                        crossMaxEnd = rightEnds[k-i];
                    }
                }

                if (crossMaxStart != -1)
                {
                    if (leftMaxStart != -1)
                    {
                        if (rightMaxStart != -1)
                        {
                            if (leftMaxSum >= rightMaxSum && leftMaxSum >= crossMaxSum)
                            {
                                maxStart = leftMaxStart;
                                maxEnd = leftMaxEnd;
                                sum = leftMaxSum;
                            }
                            else if (crossMaxSum >= leftMaxSum && crossMaxSum >= rightMaxSum)
                            {
                                maxStart = crossMaxStart;
                                maxEnd = crossMaxEnd;
                                sum = crossMaxSum;
                            }
                            else
                            {
                                maxStart = rightMaxStart;
                                maxEnd = rightMaxEnd;
                                sum = rightMaxSum;
                            }
                        }
                        else
                        {
                            if (leftMaxSum >= crossMaxSum)
                            {
                                maxStart = leftMaxStart;
                                maxEnd = leftMaxEnd;
                                sum = leftMaxSum;
                            }
                            else
                            {
                                maxStart = crossMaxStart;
                                maxEnd = crossMaxEnd;
                                sum = crossMaxSum;
                            }
                        }
                    }
                    else
                    {
                        if (rightMaxStart != -1)
                        {
                            if (rightMaxSum >= crossMaxSum)
                            {
                                maxStart = rightMaxStart;
                                maxEnd = rightMaxEnd;
                                sum = rightMaxSum;
                            }
                            else
                            {
                                maxStart = crossMaxStart;
                                maxEnd = crossMaxEnd;
                                sum = crossMaxSum;
                            }
                        }
                        else
                        {
                            maxStart = crossMaxStart;
                            maxEnd = crossMaxEnd;
                            sum = crossMaxSum;
                        }
                    }
                }
                else
                {
                    if (leftMaxStart != -1)
                    {
                        if (rightMaxStart != -1)
                        {
                            if (leftMaxSum >= rightMaxSum)
                            {
                                maxStart = leftMaxStart;
                                maxEnd = leftMaxEnd;
                                sum = leftMaxSum;
                            }
                            else
                            {
                                maxStart = rightMaxStart;
                                maxEnd = rightMaxEnd;
                                sum = rightMaxSum;
                            }
                        }
                        else
                        {
                            maxStart = leftMaxStart;
                            maxEnd = leftMaxEnd;
                            sum = leftMaxSum;
                        }
                    }
                    else
                    {
                        if (rightMaxStart != -1)
                        {
                            maxStart = rightMaxStart;
                            maxEnd = rightMaxEnd;
                            sum = rightMaxSum;
                        }
                        else
                        {
                            maxStart = -1;
                            maxEnd = -1;
                            sum = 0;
                        }
                    }
                }
            }
        }
    }
}

Answer 3

最初は、プレフィックスを使用することも考えていました（すでに言及されています）

しかし...もっと簡単な方法があると思います：

与えられた問題を説明する前に、より簡単に解決します（入力に負の数が必要です）：

最大和を持つベクトルで部分配列を見つけます。

min_sum=0
max_sum=0
sum=0
for x in elements{
  sum+=x
  if sum < min_sum { min_sum=sum }
  if sum > max_sum { max_sum=sum }
}
result=max_sum-min_sum

k1回のパスですべてのクラスに対してこれを行います

min_sum= [ array, k zeros]
max_sum= [ array, k zeros]
sum=0
for x in elements{
  sum+=x
  s = sum % k  // current numberclass
  if sum < min_sum[s] { min_sum[s]=sum }
  if sum > max_sum[s] { max_sum[s]=sum }
}
mx=0
for x in [0:k){
  s=max_sum[x]-min_sum[x]
  if(mx<s) mx=s
}

結果はmx 複雑ですO(n+k)