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

JavaLearner：

输入项

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的二维数组会导致内存不足的问题。

正义：

由于所有数字均为正数，因此唯一有效的约束条件是可除性。因此，问题是要求出最大的子数组总和，该总和可以被m盒数整除。

这可以通过以下方式完成：创建一个累加和的数组modulo 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 0 
MinMaxPos [2] =（2，3）-> sum = 4->平均= 1 
MinMaxPos [3] =（1，4）->总和= 12->平均= 3