Why do I always get an ArrayIndexOutOfBoundsException? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

This code is taken from a common algorithms book. The book uses an array starting from 1 instead of 0 for m but starts from 0 for p. How do I solve it ??

These are the errors:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
at MMC_Test.MemoizedMatrixChain(MMC_Test.java:8)
at MMC_Test.main(MMC_Test.java:36)

and code here

public class MMC_Test {

public static int MemoizedMatrixChain(int[] p) {
    int n = p.length - 1;
    int[][] m = new int[n][n];
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            m[i][j] = Integer.MAX_VALUE;
        }
    }
    return lookUpChain(m, p, 1, n);
}// MemoizedMatrixChain

public static int lookUpChain(int[][] m, int[] p, int i, int j) {
    if (m[i][j] > Integer.MAX_VALUE) {
        return m[i][j];
    }
    if (i == j) {
        m[i][j] = 0;
    } else {
        for (int k = i; k <= j - 1; k++) {
            int q = lookUpChain(m, p, i, k) 
                    + lookUpChain(m, p, k + 1, j)
                    + p[i - 1] * p[k] * p[j];
            if (q < m[i][j]) {
                m[i][j] = q;
            }
        }
    }
    return m[i][j];
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] arr = { 30, 35, 15, 5, 10, 20, 25 };
    int result = MemoizedMatrixChain(arr);
    System.out.println(result);

}// main

}

Answer 1

Change

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {

to

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {

and I haven't analyzed your code properly, but a guess is that

return lookUpChain(m, p, 1, n);

should be

return lookUpChain(m, p, 1, n - 1);

Answer 2

By creating this array:

 int[][] m = new int[n][n];

you have created a multidimensional array that ranges from:

m[0][0] => m[n-1][n-1]

There are still n spaces in the array, but we start from 0.

The problem with your code is you're using a <= operator in your for loops, when it should be a < operator.

Answer 3

index should always be till n-1.

public static int MemoizedMatrixChain(int[] p) {
    int n = p.length - 1;
    int[][] m = new int[n][n];
    for (int i = 1; i < n; i++) { //change here
        for (int j = i; j < n; j++) { //change here
            m[i][j] = Integer.MAX_VALUE;
        }
    }
    return lookUpChain(m, p, 1, n);
}// MemoizedMatrixChain

Answer 4

You have an array from 0 to (n - 1), but you use indices from 1 to n to access it. You thus do not use the first element, but try to access a non-existing element after the last.

You can see the place where it happens first in the error message (line 8). There may be further errors later in the code.

As a rule of thumb, always use indices from 0 to (n - 1), where n is the length of the array. Then your loops start from i = 0 and run while i < n. As soon as you start to add or subtract something from either bound, it should feel wrong (unless you do not want to access the whole array).