Java: Error Trying to Convert Comparable Array to Integer Array

Question

I am currently implementing a generic version of the longest increasing subsequence problem in Java. The method works as intended, but when I try to use Comparable[] instead of Integer[] (or int[]), the program won't compile. The error given is "Comparable cannot be cast to Integer". I understand the error and what it means, but I don't know how to fix it. Any help would be greatly appreciated :)

I have already tried making the method's return type a generic (>), but the problem is that Java does not allow generic array creation. I've tried just using Integer[] as my return type, and while that compiles and works properly, it's not what I want.

public class LIS {
  public static void main(String[] args) {
    final Integer[] arr = {-1, 2, 4, 2, 33, 4, 7, 8, 10, 7, 5, 4, 5, 5, 1};
    final Integer[] LIS = (Integer[]) lis(arr);
    for (int i : LIS) {
      System.out.print(i + " ");
    }
  }

  public static Comparable[] lis(Comparable[] arr) {
    // We use Comparable[] so we can use interchangably with any Comparable type

    final int N = arr.length;

    // Java conveniently initializes array values to 0:
    int[] lisEndingHere = new int[N];

    for (int i = 0; i < N; i++) {
      lisEndingHere[i] = 1;
      int curMax = 0;
      for (int j = 0; j <= i; j++) {
        if (arr[i].compareTo(arr[j]) <= 0) continue;
        if (lisEndingHere[j] > curMax) {
          curMax = lisEndingHere[j];
        }
      }
      lisEndingHere[i] += curMax;
    }

    // Find and return the longest increasing subsequence:
    int max = 0;
    for (int i = 0; i < N; i++) {
      if (lisEndingHere[i] > max) max = lisEndingHere[i];
    }

    Comparable[] LIS = new Comparable[max];
    for (int i = N-1; i >= 0 && max != 0; i--) {
      if (lisEndingHere[i] == max) {
        LIS[--max] = arr[i];
      }
    }

    return LIS;
  }
}

Answer 1

Just change the line

final Integer[] LIS = (Integer[]) lis(arr);

to

final Comparable[] LIS = lis(arr);

and also update the for loop.

Your method returns a Comparable array, so you cant downcast to an Integer array, but since the implementation of your numbers are Integers, they are still treated as such during runtime.

Setting the result to an Integer array is against the purpose of making a generic method anyways. For something to be passed to your method, it must have a compareTo method, and inherently has a toString method, and that satisfies everything you need the program to do.