求平均值最大的连续子数组

题目:

  • 一个整数数组data[n],求平均值最大的连续子数组,且子数组最少长度为k(k>1&&k<n)
  • 如:[3,6,2,5,7,1] 平均值最大的连续子数组为:[6,2,5,7]

解题思路:

xxx


参考代码:


public class Test1 {
    public static void main(String[] args) {
        int[] data = new int[]{6, 5, 6, 9, 4, 8, 7, 7, 1, 4};

        int n = data.length;
        int k = 3;

        int[] maxSumArray = new int[k];
        double maxMean = handle(data, n, k, maxSumArray);

        int[] tempSumArray;
        double tempMean;
        for (int i = k + 1; i < 2 * k & i < n; i++) {
            tempSumArray = new int[i];
            tempMean = handle(data, n, i, tempSumArray);
            if (tempMean > maxMean) {
                maxMean = tempMean;
                maxSumArray = tempSumArray;
            }
        }

        System.out.println("max mean: " + maxMean);
        System.out.print("sub array: ");
        for (int i = 0; i < maxSumArray.length; i++) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(maxSumArray[i]);
        }

    }

    public static double handle(int[] data, int n, int k, int[] result) {
        int sumMax = 0;
        int pLeftMax = 0;
        int pRightMax = k - 1;

        //init first kth element sum
        for (int i = 0; i < k; i++) {
            sumMax += data[i];
        }

        int sum = sumMax;
        int pLeft = pLeftMax;
        int pRight = pRightMax;
        for (int i = k; i < n; i++) {
            sum -= data[pLeft];
            pLeft++;
            pRight++;
            sum += data[pRight];

            if (sum > sumMax) {
                sumMax = sum;
                pLeftMax = pLeft;
                pRightMax = pRight;
            }

        }

        for (int i = 0; i < k; i++) {
            result[i] = data[pLeftMax + i];
        }

        double mean = Double.valueOf(sumMax) / k;
        return mean;

    }
}





个人资料
尘封记忆
等级:5
文章:5篇
访问:5.3k
排名: 29
推荐圈子
上一篇: 阿里巴巴集团2014秋季校园招聘笔试题
下一篇:2017百度校园招聘笔试面试题
猜你感兴趣的圈子:
每日一算法
标签: summax、maxsumarray、maxmean、tempsumarray、tempmean、面试题
隐藏