java - 数组子序列的最大可能平均值——需要有效的解决方案

Question

输入

1: array size (1 to 10^5)
2: Number to take average (1 to 10^3)
3: elements in array (1 to 10^5) Non sorted, any order is possible

输出：任何子数组的最大可能平均值。

Eg:
5 3
1 2 3 4 5
o/p = 5

5 4
1 2 3 4 5
o/p = 3

for first example seq will be sum[0,4]=15 and its average with 3 will be 5.
for second example seq will be sum[2,4]=12 and its average with 4 will be 3.

我已经在下面给出了 o(n^2) 的解决方案，但它不适用于大输入。

            long max = 0;
            for( int m = 0; m < people; m++ )
            {
                long sum = 0;
                for( int n = m; n < people; n++ )
                {
                    sum = sum + chocolateArray[n];
                    if( sum % boxes == 0 )
                    {
                        if( ( sum / boxes ) > max )
                        {
                            max = sum / boxes;
                        }
                    }
                }
            }
            System.out.println( max );

其中people是数组大小，boxes是平均数，chocolateArray是原始数组。

请提供有效的解决方案。我想通过它，dynamic programming但创建 10^5 大小的二维数组会导致内存不足问题。

标签： javaalgorithm

Answer 1

由于所有数字都是正数，因此唯一有效的约束是可分性。所以问题是要求可以被 整除的最大子数组和，即m盒子的数量。

这可以通过创建一个累积和模的数组来完成m，然后找到两个具有相同数字的位置，并且尽可能地相距较远。由于最多有m值，我们可以简单地存储每个可能的残差的最小和最大索引，然后取具有最大子数组和的那个。下面的代码就是这样做的。

cumsum = int[people+1];
minPos = int[boxes];
maxPos = int[boxes];
Arrays.fill(minPos, -1);
Arrays.fill(maxPos, -1);
int residue = 0;
for(int i=0; i<people; i++){
    cumsum[i+1] = cumsum[i] + chocolateArray[i]; // For simplicity the array length is 1 longer
    residue = cumsum[i+1] % boxes;
    if(minPos[residue] == -1) minPos[residue] = i;
    maxPos[residue] = i;
}
int max = 0;
for(int i=0; i<boxes; i++){
    int sum = cumsum[maxPos[i]+1] - cumsum[minPos[i]+1];
    if(sum > max){
        max = sum;
    }
}
System.out.println(max/boxes);

例如：

人 = 5
盒子 = 4
数组 = [1, 2, 3, 4, 5]
累积 = [1, 3, 6, 10, 15]
残基 = [1, 3, 2, 2, 3]
MinMaxPos[0] = (-1, -1) -> sum = 0 -> avg = 0
MinMaxPos[1] = (0, 0) -> sum = 0 -> avg = 0
MinMaxPos[2] = (2, 3) -> sum = 4 -> avg = 1
MinMaxPos[3] = (1, 4) -> sum = 12 -> avg = 3