私たちのほとんどは、部分配列の最大和問題に精通しています。私はこの問題の変種に遭遇しました。これは、ある数 M を法とするすべての部分配列の和の最大値を出力するようにプログラマーに要求するものです。
このバリアントを解決するための素朴なアプローチは、可能なすべての部分配列の合計を見つけることです (N は配列のサイズである N^2 のオーダーになります)。もちろん、これでは十分ではありません。問題は、どうすれば改善できるかということです。
例: 次の配列を考えてみましょう。
6 6 11 15 12 1
M = 13 とします。この場合、サブアレイ 6 6 (または 12 または 6 6 11 15 または 11 15 12) は最大合計 ( = 12 ) を生成します。
これは次のように行うことができます。
sumindexithに 0 から までの係数の合計を含む配列を維持しithます。
各 index についてith、このインデックスで終わる最大の小計を見つける必要があります。
各部分配列 (start + 1 , i ) について、この部分配列の mod 合計が
int a = (sum[i] - sum[start] + M) % M
したがって、が よりも大きく、可能な限り近いsum[i]場合にのみ、 よりも大きな部分合計を達成 できます。sum[start]sum[i]sum[i]
二分探索木を使えば簡単にできます。
擬似コード:
int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
sum[i] = sum[i - 1] + A[i];
sum[i] %= M;
int a = tree.getMinimumValueLargerThan(sum[i]);
result = max((sum[i] - a + M) % M, result);
tree.add(sum[i]);
}
print result;
時間計算量 :O(n log n)
私にとって、検索/ソートの部分がわからなかったので、ここでの説明はすべてひどいものでした。検索/ソートの方法が不明でした。
を構築する必要があることは誰もが知っていますprefixSum。sum of all elems from 0 to i with modulo m
私たちが探しているものは明らかだと思います。(インデックス i から j までのモジュロ合計を示す)ことを知っているとsubarray[i][j] = (prefix[i] - prefix[j] + m) % m、prefix[i] が指定されたときの最大値は常に、prefix[i] にできるだけ近いが、わずかに大きい、その prefix[j] です。
たとえば、m = 8 の場合、prefix[i] が 5 の場合、prefixArray にある 5 の次の値を探します。
効率的な検索 (バイナリ検索) のために、接頭辞を並べ替えます。
できないことは、最初に prefixSum を構築し、次に 0 から n まで繰り返して、並べ替えられたプレフィックス配列でインデックスを探すことです。
したがって、潜在的な最大部分配列合計のendIndexを示す 0 から n まで反復し、0 と endIndex の間の並べ替えられた接頭辞を含む並べ替えられた接頭辞配列 (最初は空) を調べます。
def maximumSum(coll, m):
n = len(coll)
maxSum, prefixSum = 0, 0
sortedPrefixes = []
for endIndex in range(n):
prefixSum = (prefixSum + coll[endIndex]) % m
maxSum = max(maxSum, prefixSum)
startIndex = bisect.bisect_right(sortedPrefixes, prefixSum)
if startIndex < len(sortedPrefixes):
maxSum = max(maxSum, prefixSum - sortedPrefixes[startIndex] + m)
bisect.insort(sortedPrefixes, prefixSum)
return maxSum
O(n*log(n)) を使用した完全な Java 実装
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.stream.Stream;
public class MaximizeSumMod {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Long times = Long.valueOf(in.readLine());
while(times --> 0){
long[] pair = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
long mod = pair[1];
long[] numbers = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
printMaxMod(numbers,mod);
}
}
private static void printMaxMod(long[] numbers, Long mod) {
Long maxSoFar = (numbers[numbers.length-1] + numbers[numbers.length-2])%mod;
maxSoFar = (maxSoFar > (numbers[0]%mod)) ? maxSoFar : numbers[0]%mod;
numbers[0] %=mod;
for (Long i = 1L; i < numbers.length; i++) {
long currentNumber = numbers[i.intValue()]%mod;
maxSoFar = maxSoFar > currentNumber ? maxSoFar : currentNumber;
numbers[i.intValue()] = (currentNumber + numbers[i.intValue()-1])%mod;
maxSoFar = maxSoFar > numbers[i.intValue()] ? maxSoFar : numbers[i.intValue()];
}
if(mod.equals(maxSoFar+1) || numbers.length == 2){
System.out.println(maxSoFar);
return;
}
long previousNumber = numbers[0];
TreeSet<Long> set = new TreeSet<>();
set.add(previousNumber);
for (Long i = 2L; i < numbers.length; i++) {
Long currentNumber = numbers[i.intValue()];
Long ceiling = set.ceiling(currentNumber);
if(ceiling == null){
set.add(numbers[i.intValue()-1]);
continue;
}
if(ceiling.equals(currentNumber)){
set.remove(ceiling);
Long greaterCeiling = set.ceiling(currentNumber);
if(greaterCeiling == null){
set.add(ceiling);
set.add(numbers[i.intValue()-1]);
continue;
}
set.add(ceiling);
ceiling = greaterCeiling;
}
Long newMax = (currentNumber - ceiling + mod);
maxSoFar = maxSoFar > newMax ? maxSoFar :newMax;
set.add(numbers[i.intValue()-1]);
}
System.out.println(maxSoFar);
}
}
ウィキペディアで読むことができるように、Kadane のアルゴリズムと呼ばれるソリューションが存在します。これは、配列を 1 回反復することにより、すべての位置iについて位置iで終わる最大サブ配列の合計を監視する最大サブ配列合計を計算します。次に、これにより、実行時の複雑さ O(n) の問題が解決されます。
残念ながら、Kadane のアルゴリズムは、複数の解が存在する場合、すべての可能な解を見つけることができないと思います。
Javaでの実装、私はそれをテストしませんでした:
public int[] kadanesAlgorithm (int[] array) {
int start_old = 0;
int start = 0;
int end = 0;
int found_max = 0;
int max = array[0];
for(int i = 0; i<array.length; i++) {
max = Math.max(array[i], max + array[i]);
found_max = Math.max(found_max, max);
if(max < 0)
start = i+1;
else if(max == found_max) {
start_old=start;
end = i;
}
}
return Arrays.copyOfRange(array, start_old, end+1);
}
私の考えはすでに投稿されているものと一致していると思いますが、念のため- Kotlin O(NlogN) ソリューション:
val seen = sortedSetOf(0L)
var prev = 0L
return max(a.map { x ->
val z = (prev + x) % m
prev = z
seen.add(z)
seen.higher(z)?.let{ y ->
(z - y + m) % m
} ?: z
})
#occurrence を追跡するために Kadaneアルゴリズムを変更します。以下はコードです。
#python3
#source: https://github.com/harishvc/challenges/blob/master/dp-largest-sum-sublist-modulo.py
#Time complexity: O(n)
#Space complexity: O(n)
def maxContiguousSum(a,K):
sum_so_far =0
max_sum = 0
count = {} #keep track of occurrence
for i in range(0,len(a)):
sum_so_far += a[i]
sum_so_far = sum_so_far%K
if sum_so_far > 0:
max_sum = max(max_sum,sum_so_far)
if sum_so_far in count.keys():
count[sum_so_far] += 1
else:
count[sum_so_far] = 1
else:
assert sum_so_far < 0 , "Logic error"
#IMPORTANT: reset sum_so_far
sum_so_far = 0
return max_sum,count[max_sum]
a = [6, 6, 11, 15, 12, 1]
K = 13
max_sum,count = maxContiguousSum(a,K)
print("input >>> %s max sum=%d #occurrence=%d" % (a,max_sum,count))