How to determine if a subarar has a specific sum inside a 2D array in Java?

Question

I am trying to solve the problem of image matching by comparing the average color of pixels present both in the source image and in the sample. I reduced this problem to the problem of the total array, but I can not find a way to solve it.

Suppose I have an ARR of a 2D array with all positive integers. I have a number x (the average of the colors of the pixels present in a small sample). I just need to find some subarray in ARR that has the exact sum of x. I found a similar problem that could be solved using dynamic programming here.

http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

But this indicates the finding of a subarray with the maximum amount , and not the amount that has already been given.

  So if this the given array.

 3 4 8 9 3
 2 10 4 2 1
 8 1 4 8 0
 3 5 2 12 3
 8 1 1 2 2

 And if the given sum is 19, then it should return this window

 3 4 8 9 3
 2 10 4 2 1
 8 1 4 8 0
 3 5 2 12 3
 8 1 1 2 2

 And if the given sum is 23, then it should return this window

 3 4 8 9 3
 2 10 4 2 1
 8 1 4 8 0
 3 5 2 12 3
 8 1 1 2 2

How can I find this efficiently? Can dynamic programming be used here? Please help me here.

Answer 1

Using the same principle, but for a simpler problem. First, I precommute the cumulative sum for each column array, i.e. A [i] [j] + = A [i-1] [j].

Then, for each pair of start / end lines (i1, i2), I consider them as a single array B [j], which means B [j] = A [i2] [j] - A [i1-1] [J]. Then we need to find a subarray with the exact sum. Since the array consists of only positive numbers, I can find it in O (n).

In general, this algorithm is O (n ^ 3).

For the values ​​you provided, I managed to find several arrays of additional data:

For target = 19:

Found between (0,0) and (1,1) Found between (0,3) and (2,4) Found between (0,2) and (4,2) Found between (1,1) and (2,2) Found between (1,2) and (2,4) Found between (2,0) and (4,0) Found between (3,3) and (4,5) 

Target = 23:

 Found between (0,2) and (1,3) Found between (0,3) and (2,4) Found between (2,0) and (3,2) Found between (2,3) and (3,4) Found between (3,1) and (4,4) 

The code I used:

 public static void main(String[] args) { int[][] A = { {3, 4, 8, 9, 3}, {2, 10, 4, 2, 1}, {8, 1, 4, 8, 0}, {3, 5, 2, 12, 3}, {8, 1, 1, 2, 2}, }; int target = 19; for (int i = 1; i < A.length; i++) for (int j = 0; j < A[i].length; j++) A[i][j] += A[i - 1][j]; for (int i1 = 0; i1 < A.length; i1++) { for (int i2 = i1 + 1; i2 < A.length; i2++) { int j1=0, j2=0, s=0; while(j2<A[i1].length) { while(s<target && j2<A[i1].length) { s += A[i2][j2] - (i1 > 0 ? A[i1-1][j2] : 0); j2++; if (s==target) System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2-1)); } while(s>=target) { s -= A[i2][j1] - (i1 > 0 ? A[i1-1][j1] : 0); j1++; if (s==target) System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2)); } } } } }