Google - 2

Question

输入是一个array of numbers，一个size, 输出这个size的一个window (start, end) 所包含数字的和,最大

Algorithm

• use maxSum variable holding the maximum window sum up to current number
• use tempSum variable holding the sum of numbers in window
• traverse number in the input array from the first number
  • up to the number whose index is size - 1, we just add the number to tempSum
  • if current number whose index is size - 1, we set maxSum equal to tempSum
  • otherwise we add the current number to tempSum and minus the first number in window, and update maxSum

Complexity

• time complexity: O(N)
• space complexity: O(1)

Code

public int findMaxSum(int[] nums, int size) {
    int length = nums.length;
    int maxSum = Integer.MIN_VALUE;
    int tempSum = 0;
    for (int i = 0; i < length; i++) {
        if (i < size) {
            tempSum += nums[i];
            if (i == size - 1) {
                maxSum = tempSum;
            }
        } else {
            tempSum += nums[i] - nums[i - size];
            maxSum = Math.max(maxSum, tempSum);
        }
    }
    return maxSum;
}

Follow Up

2-d array, size => find a 2-d window.

Algorithm

• create a 2d array called sum
  • sum[i][j] means sum of elements in input array row from 0 to i -1 and column from 0 to j - 1
  • sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j -1] + nums[i][j];
• use maxSum variable holding the maximum sum up to current window
• traverse the rectangles in input array
  • the bottom right index of window is i ,j
  • the top left index of window is i - size, j - size
  • sum of elements in window is
    • sum[i][j] - sum[i][j - size] - sum[i - size][j] + sum[i - size][j - size];
  • update maxSum

Code

public int findMaxSum(int[][] nums, int size) {
    if (nums == null || nums.length == 0 || nums[0].length == 0) {
        return 0;
    }
    int maxSum = Integer.MIN_VALUE;
    int width = nums[0].length;
    int height = nums.length;
    int[][] sum = new int[height + 1][width + 1];
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + nums[i - 1][j - 1];
        }
    }
    for (int i = size; i <= height; i++) {
        for (int j = size; j <= width; j++) {
            int tempSum = sum[i][j] - sum[i][j - size] - sum[i - size][j] + sum[i - size][j - size];
            maxSum= Math.max(tempSum, maxSum);
        }
    }
    return maxSum;   
}