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;
}