3

我一直在练习算法问题，我遇到了这个问题。
给定一个数组（包含 +ve 和 -ve）数字，我必须找到一个连续的子数组，使得总和可以被任何数 K 整除，并且子数组应该是可能的最大总和。例如。
a={1,2,2,1,1,4,5,3}并且k=5可以被 k 整除的最大和子数组
{2,2,1,1,4,5}, sum = 15
目前我能想到的是，每个元素都有两种可能性，要么将其包含在目标子数组中，要么不包含在目标子数组中。但这将是一个指数算法。
编辑：是否有可能在线性时间解决这个问题。请帮忙

4

4 回答 4

3

这个问题的关键词是前缀总和。

计算它们的伪代码如下所示：

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 整除。现在要找到最大总和子数组，我们查看每个元素一次。当我们查看每个元素一次时，我们会做 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]我们将索引存储i在中。现在我们有能力在 O(1) 中查找具有最大前缀和的索引，该索引具有给定的余数。max_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)，并且由于前缀 sum，它应该适用于负数和正数。

于 2013-08-01T09:19:30.327 回答
1

如果不是负数，则每个总和可被 K 整除的连续子数组应该由最多包含 K 个元素的较小和可整子子数组组成。但是对于负数，这是不正确的。

所以基本上唯一的选择是检查每个子数组的总和是否可以整除。像这样：

a = [1,2,2,1,1,4,5,3]
K = 5

max_a = []
max_len = 0

for i in range(len(a)):
    for j in range(i+1, len(a)+1):
        s = sum(a[i:j])
        if s % K == 0 and j-i > max_len:    
            max_len = j-i
            max_a = a[i:j]

print max_a

嗯，它是多项式的，但仍然不是很有效。

于 2013-08-01T05:36:55.030 回答
0

我为此写了一个分而治之的算法。

如果 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

FindMaxCrossingSubarrayDivisible可以使用 O(k) 存储在 O(max(n,k)) 时间内完成。我的想法是有一个 k 整数数组，其中每个元素存储余数 i 数组右侧的最大交叉和，其中 0 <= i < k。对数组的左侧执行相同的操作，然后在 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;
                        }
                    }
                }
            }
        }
    }
}
于 2013-08-01T07:49:05.463 回答
0

起初我也考虑过使用前缀（已经提到过）

但是...我认为有一个更简单的方法：

在我描述给定的问题之前，我解决了一个更简单的问题（我希望输入中有负数）：

在具有最大和的向量中找到子数组：

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

我将k在一次通过期间为所有课程执行此操作

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)

于 2013-08-02T05:45:49.073 回答